Essays/Binary GCD Algorithm
< Essays
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 265252859812191058636308480000000 (!40x) +. !30x 265252859812191058636308480000000 (!40x) bgcd&>: !30x 1 (!40x) +.&>: !30x 1
See also
Contributed by Roger Hui.