Wednesday, 19 March 2008

Lagged Fibonacci Pseudo-Random Generator

If you need a pseudo-random number generator which works regardless of the coresize, a Lagged Fibonacci generator is one of the better options.

Here's an implementation in 3 instructions with _rndj fixed at 1. _rndk can take the values 3, 4, 6, 7, 15, 22, 60 or 63 depending on the period required. With _rndk = 4 and coresize 8000, the period is 31200.

For more variations, see the Wikipedia article on Lagged Fibonacci generators.
           _rndk  equ 4

random mov.a >rdata, random_out
mod.ab #_rndk, rdata
add.a *stack, @rdata

rdata dat 3711, 0
dat 1674, 0
dat 4323, 0
dat 7835, 0

Saturday, 8 March 2008


Calculates the sign of location's b-field, returning -1, 0 or 1.
sign      jmz.b  done,           location
slt.b location, #1+CORESIZE/2
mov.ab #-1, location
seq.ab #-1, location
mov.ab #1, location

Absolute Value

This two-line redcode snippet returns the absolute value of location's b-field.
abs       slt.b  location,       #1+CORESIZE/2
mul.ab #-1, location

Tuesday, 4 March 2008

Euclid's extended

The extended Euclidean algorithm is used to calculate x and y given a and b in the following equation:

ax + by = gcd(a,b)

Implementation in Redcode:
          org    start

temp equ r-1

r dat 55, 89 ; input a b - output gcd(a,b)
s dat 1, 0
t dat 0, 1 ; output x y

euclidext mov r, temp
div.ab temp, temp temp, temp
mul s, temp
sub temp, t

mov s, temp
mov t, s
mov temp, t

mod.ab r, r
mov.x r, r
start jmn.a euclidext, r