SICP: Exercise 1.26

問題 1.26

Louis Reasoner は問題 1.24 がなかなかうまくいかなかった. 彼の fast-prime? は prime? よりずっと遅いようであった。Louis は友人の Eva Lu Ator に助けを求めた。Louis のプログラムを見ていると、square を呼び出す代りに乗算を陽に使うように変っていた。

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (* (expmod base (/ exp 2) m)
                       (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))

「違いが分らん」と Louis、「分る」と Eva がいった。「手続きをこのように書き替えたので、\( \Theta(\log n) \) のプロセスを \( \Theta(n) \) のプロセスにしてしまった。」説明せよ。

「計算機プログラムの構造と解釈 第二版 1.2.6 例：素数性のテスト」より

expmod の exp に注目し、どのように手続きが呼び出されるか考える。

square を使う

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))

の場合、以下の図のように呼び出される。段階数は \( \Theta(\log n) \)。

一方、Louis の

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (* (expmod base (/ exp 2) m)  ; (*)
                       (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))

の場合、(*) の部分に到達するたびに expmod が 2 回呼び出されるので、以下の図のようになる。

図で比較すると、Louis の書き方のまずさがよく分かる。(*) に到達する回数は \( \Theta(\log_2 n) \) であり、そこで経路が 2 つに分かれるので、全体の段階数は

$$ \Theta\left( 2^{\log_2 n} \right) = \Theta(n) $$

となる。