問題1.24~問題1.26

問題1.24

　fast-primeの試行回数に正解はないのですが、ここでは200としています。
比較するのはnが1000近傍の場合と、(1000）^2 = 1000000近傍での処理時間の比較です。そのため、比較結果は試行回数に依存しません。log n^2 = 2log nのため、おおよそ2倍となると予測されます。

(define (start-prime-test n start-time)
  (if (fast-prime? n 200)
      (report-prime (- (runtime) start-time))))

> (timed-prime-test 1009)

1009 *** 857
> (timed-prime-test 1013)

1013 *** 749
> (timed-prime-test 1019)

1019 *** 782
> (timed-prime-test 10007)

10007 *** 924
> (timed-prime-test 1000003)

1000003 *** 1202
> (timed-prime-test 1000037)

1000037 *** 1239
> (timed-prime-test 1000033)

1000033 *** 1390

> 

　2倍程度とみて問題ないので、これは予想を支持する結果となりました。ただ、fast-prime?のはずなのにprime?よりは大幅に遅くなってしまいました。これは試行回数に依存する値になるので直接の比較はできません。

　prime?ではnが100倍になるとおよそ10倍時間がかかっていたので、それよりはかなり改善がなされています。

問題1.25

;全問の1390に対して圧倒的に遅いです。
> (timed-prime-test 1000033)

1000033 *** 409890338

　当然、両者とも同じ答えを出します。ただ手続き上、expを用いた場合は小さな値に対するremainderを何度も繰り返しますが、fast-exptの場合は大きな値に対するremainderを1度だけ実行します。

　これはschemeの場合remainderの桁数が大きいと計算に非常に時間がかかるからだそうです（そんなの知らんがな）。

　ということは最適な計算を実施したい場合は、計算方法の処理速度の違いに応じて最適なプログラムを書き換える必要があるという結果になります…

問題1.26

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

　上の手続きにおいてsquareの代わりにexpmodeを2度呼び出している。
これは再帰的木構造のフィボナッチ数を求める手続き（下の式参照）と同じで指数的にステップ数が増加する

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

　本来expmodは対数的に増加するので、O(log(2^n) ) = O(n)　のプロセスとなる。