ochalog

RubyとMediaWikiとIRCが好き。

SICP: Exercise 1.25

問題 1.25

Alyssa P. Hacker は expmod を書くのに多くの余分なことをやったと不満で、結局べき乗の計算法は知っているから

(define (expmod base exp m)
  (remainder (fast-expt base exp) m))

と単純に書ける筈だといった。これは正しいか。これも高速素数テストと同じに使えるか、説明せよ。

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

正しくない。

これが正しくないことは、expmod を大きな exp に対して行うことで分かる。試しに \( 5^{10000000} \mod 10000000 \) を計算してみよう。まず問題 1.16 から繰り返しプロセスの fast-expt を持ってきて、Alyssa が示した expmod を実行する。

(define (fast-expt b n)
  (define (fast-expt-iter a b n)
    (cond ((= n 0) a)
          ((even? n) (fast-expt-iter a
                                     (square b)
                                     (/ n 2)))
          (else (fast-expt-iter (* a b)
                                b
                                (- n 1)))))
  (fast-expt-iter 1 b n))

(define (expmod base exp m)
  (remainder (fast-expt base exp) m))

(expmod 5 10000000 10000000)
; なかなか終わらない…

一方、本文で示された expmod を使えば

(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))))

(expmod 5 10000000 10000000)
; 2890625(一瞬で出る)

となり、計算時間に大きな差がある。

fast-expt を使うと最終的にとても大きい数を \( m \) で割った余りを求めることになるので、計算が遅くなったり桁あふれが起こる可能性がある。各段階で remainder を適用すれば、脚注 46 で

指数 \( e \) が 1 より大きい場合の簡約化では、任意の整数 \( x \)、\( y \) と \( m \) について、\( x \times y \mod m \) の剰余は、\( x \mod m \) と \( y \mod m \) の剰余を別々に計算し、その結果を掛け合せ、更に積の \( \mod m \) の剰余をとればよいという事実に基づいている。\( e \) が偶数の場合は、\( b^{e/2} \mod m \) の剰余を計算し、二乗し、その \( \mod m \) の剰余をとる。これは \( m \) より遥かに大きい数値を扱わずに計算が実行出来、有用である。

と指摘されているように、\( m^2 \) 以上の数を扱わずに計算できるので、上記の問題が生じない。