1.2.5 最大公約数

文責:@naoiwata

2 つの整数 a と b の最大公約数(GCD)を効率的に見つけるアルゴリズムを考える. a を b で割った剰余を r とすると, 公約数は b と r の公約数と同じという考えに基づいて以下の式が定義できる.

; Euclid's algorithm
(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

ステップ数は対数的に増加する.