Scheme - 手続きとその生成するプロセス(例: 素数性のテスト(remainderと速度、squareと乗算、プロセス))

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Lion - Apple(OS)
• Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
• プログラミング言語: MIT/GNU Scheme

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション)の1(手続きによる抽象の構築)、1.2(手続きとその生成するプロセス)、1.2.6(例: 素数性のテスト)の問1.25、1.26を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題 1.25.

書き直す前のは、剰余の剰余の…にremainderを使う事になるので、比較的小さい数(最大でも(square base)に何回もremainderを使う事になる。fast-exptを使って書き直した後は、base^expを求めてから、その大きな数に一度remainderを使う事になる。結果は同じだけど、速度はremainderの速度に関係してきそう。ということで、実際に計測してみる。

コード

sample.scm

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

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

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

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

1 ]=> 
(expmod 10 1 11)
(expmod 10 2 11)
(expmod 10 3 11)
(expmod 10 4 11)
(expmod 10 5 11)

(expmod-fast-expt 10 1 11)
(expmod-fast-expt 10 2 11)
(expmod-fast-expt 10 3 11)
(expmod-fast-expt 10 4 11)
(expmod-fast-expt 10 5 11)

;Value: 10

1 ]=> 
;Value: 1

1 ]=> 
;Value: 10

1 ]=> 
;Value: 1

1 ]=> 
;Value: 10

1 ]=> 
;Value: 10

1 ]=> 
;Value: 1

1 ]=> 
;Value: 10

1 ]=> 
;Value: 1

1 ]=> 
;Value: 10

1 ]=> (expmod 10 10000000000 11)

;Value: 1

1 ]=> (expmod-fast-expt 10 10000000000 11)
^C
Interrupt option (? for help): ^C
;Quit!

1 ]=> 

小さめの数で確認したら結果は同じ。大きな数で確認しようとしたら、fast-exptを使って書き換えた方は計算に時間がかかってるみたいなので中断。大きな数になるとremainderは遅くなるみたい。なので、fast-exptを使って単純に書き換えたのは高速素数テストに同じようには使えない。

問1.26

偶数の場合の評価で、sqaureでは手続きexpmodを使うのは一度だけど、乗算使ったら手続きexpmodを2度使うことになる。ということで、手続きを書き換えたら、n log n / 2倍のステップ数になり、Θ(log n)のプロセスをΘ(n)のプロセスにしてしまったからずっと遅くなった。