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 2^{R} 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:

- Let C = A—B.
C will be even.
If C is zero, either A or B, times 2

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