Just now I do not find Rollo Silver’s GCD Algorithm on the web. I thought it was pretty well known but these days it is not know unless it is on the web. This is a remarkable algorithm for it is an improvement on arguably the oldest mathematical algorithm; Euclid described how to find the GCD of two natural numbers, but he used division.
Since numbers are naturally binary, dividing even numbers by two does not count as division. Count the number of zeros at the right of both numbers. Call the minimum of these counts R. Shift both numbers right until odd. (The answer is 2R times the GCD of the two odd new numbers.) We have two odd numbers; let A be the larger and B be the smaller. We repeat the following:
The number of steps is somewhat larger than for Euclid’s algorithm, but subtracting and shifting are much faster than division. Perhaps I learned this from Knuth’s Semi-Numerical Algorithms where he considers the performance of this algorithm.
(define (G A B) (let ((cz (lambda (x) (let cz ((zc 0)(x x)) (if (odd? x) (cons zc x) (cz (+ zc 1)(/ x 2))))))) (let ((A (cz A))(B (cz B))) (let ((A (cdr A))(B (cdr B))(R (min (car A) (car B)))) (let loop ((A (max A B))(B (min A B))) (let ((C (- A B))) (if (zero? C) (* (expt 2 R) A) (let ((C (cdr (cz C)))) (loop (max B C) (min B C)))))))))) (define p 6700417) ; prime (define A 547892039487896) ; big num (define B 304579820978903983476) ; bigger num (G A B) ; => 4 (G (* p A) (* p B)) ; => 4*p