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