(defun *gcd (x y &optional (acc 1) (count 0))
  (incf count)
  (cond ((= x y)
         (values count (* acc x)))
        ((and (oddp x) (oddp y)) ; odd, odd
         (*gcd (min x y) (ash (abs (- x y)) -1) acc count))
        ((oddp x) ; odd, even
         (*gcd x (ash y -1) acc count))
        ((oddp y) ; even, odd
         (*gcd (ash x -1) y acc count))
        (t ; even, even
         (*gcd (ash x -1) (ash y -1) (ash acc 1) count))))

(defun fib (x)
  (loop with l = '(1 1) for i from 2 to x
    do (push (+ (car l) (cadr l)) l)
    finally (return (car l))))

(format t "~{Called ~D times, result is ~D~}"
        (multiple-value-list (*gcd (fib 2000) (fib 1999))))