SICPを読む(17) 問題1.24 - 1.28 randomが・・・。

MzSchemeのrandomはINT_MAXの範囲でしか使えない。

random: expects argument of type <exact integer in [1, 2147483647]>; given 10000000006

intの制限越えちゃってますよ・・・と。

問題1.24

仕方ないので、テスト回数を増やして対応する。

(define (timed-prime-fast-test n times)
 (newline)
 (display n)
 (start-prime-fast-test n times (runtime)))
(define (start-prime-fast-test n times start-time)
 (if (fast-prime? n times)
     (report-prime (- (runtime) start-time))))

(timed-prime-fast-test 1000000007 200) ; 0.020秒

前問のテスト結果と比べると、約200倍早い。高速化以前と比べると、400倍早い。

~~$\sqrt{n}$ にはなってないが、フェルマーテストが高速であることが確認できた。~~

追記

ステップ数の計算が間違ってました。フェルマーテストは $log_{2}n$ の増加なので、

(/ (sqrt 1000000007) 2) ; 15811
(* 200 (/ (log 1000000007) (log 2))) ; 5979

力業法だと、1万5千回。フェルマーテストは5千回。それを0.02秒で計算する。

3倍違うな・・・。200回という数を時間から逆算しているので、相当誤差があると思う。

まぁ、大体 $log_{2}n$ になることが確認できた。

底の変換公式メモ。

(/ (log 8) (log 2)) ; 3.0

で、2を底にとる、8の対数が取れる。

式に直すと、こんな感じ。

$log_{2}{3} = \frac{log_{e}8}{log_{e}2}$

うはぁ。

一般的に直すと、

$log_{b}{c} = \frac{log_{a}c}{log_{a}b}$

って感じ。底の変換公式。

覚えにくいので、Schemer的。底の変換公式。

(/ (log 値) (log 底))

グレイトにスッキリ!!

またひとつ賢くなりました。

問題1.25

外れた・・・。

問題1.26

2回実行してるので、意味なし。

問題1.27,1.28

ホントに騙されてる事は確認できた。

(smalltest-divisor 561) ; 3
(timed-prime-fast-test 561 10000) ; 561

問題の意味がよくわからないので、飛ばす。