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
mov.ba 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

1 comment:

oyvind said...

Heyas! Nice blog, I saw you signed up at Entrecard and I got curious.

I've never heard of Corewars until now. I tried to find out how you guys compile these warriors, I guess you need to test them before submitting them? I'd love to learn.

Do you have a kind of playground to submit them to on your localhost?

I have programmed since zx81 (the one with 1k mem) so I'm embarrased to say that I've never heard of Corewars. Oh well, never too late!

Oh, does the warriors get autoinserted, compiled and started when submitted or does webmaster have to check them for errors first?

Sorry about the many noob questions..