SICP: Exercise 1.25
問題 1.25
Alyssa P. Hacker は
expmod
を書くのに多くの余分なことをやったと不満で、結局べき乗の計算法は知っているから(define (expmod base exp m) (remainder (fast-expt base exp) m))
と単純に書ける筈だといった。これは正しいか。これも高速素数テストと同じに使えるか、説明せよ。
正しくない。
これが正しくないことは、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 \) 以上の数を扱わずに計算できるので、上記の問題が生じない。