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

Euclid's algorithm

Euclid's algorithm is used to determine the Greatest Common Divisor of two values. Despite it's simplicity, the only previous redcode implementation I can find is broken.

Implementation in Redcode:

          org    euclid+2

euclid    mod.ab #a,                #b
          mov.x  euclid,            euclid
          jmn.a  euclid,            euclid