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^R, will be the answer to the original problem. Otherwise shift C right until it is odd. Rename max(B, C) as A and min(B, C) as B and repeat. The GCD of our two numbers has not changed.

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