Essays/Binary GCD Algorithm

From J Wiki
Jump to navigation Jump to search

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
   (!40x) +. !30x
   (!40x) bgcd&>: !30x
   (!40x) +.&>: !30x

See also

Contributed by Roger Hui.