Essays/Binary GCD Algorithm

The binary GCD algorithm is described in Eric Bach and Jeffrey Shallit, Algorithmic Number Theory, Volume I: Efficient Algorithms, MIT Press, 1996, Section 4.7. It is based on the following facts:

• if x and y are both even, then  (x+.y) = x +.&.-: y
• if x is odd and y is even, then  (x+.y) = x +. -:y
• if x and y are both odd, then   (x+.y) = x +. -:|x-y

Therefore, for positive integers,

huo=: -:^:(0=2&|)^:_  NB. halve until odd

bgcd=: 4 : 0
 g=. 1 [ v=. x,y
 while. 0 0 -: 2|v do. g=. +:g [ v=. -:v end.
 v=. huo"0 v
 while. {.v do. v=. v (</v)}~ huo |-/v end.
 g * {:v
)

   (!40x) bgcd !30x
265252859812191058636308480000000
   (!40x) +. !30x
265252859812191058636308480000000
   (!40x) bgcd&>: !30x
1
   (!40x) +.&>: !30x
1

---

See also

• Wikipedia
• Euclidean Algorithm
• Gaussian Integers

---

Contributed by Roger Hui.