SICP 読み (10)
1 章再読は途中で止めて 2 章に移りたい欲求に耐えつつ、今日もオレオレ 20%。
問題 1.23 (つづき)
9 桁では約半分だが、10 桁以降は約 1/3 (より少ないが) 程度のスピード短縮。桁数が多い方が信頼性は高いと考えると、11 桁で約 62.5 % の短縮となっている。
ただ、これって 11 桁の最初らへんの素数という意味では、これで妥当なんじゃね? と思ってしまうんだけど、ダウトなのだろうか。例えば 11 桁の後半部分 (しかも 12 桁に限りなく近い) な数値だったら 5 割を切ってしまう、とか。
あ、やってみれば良いのか。
以下、変更した手続きのみ。
(define (test-timed-prime-test)
;; (let f ((l (reverse (search-for-prime '(100000000 1000000000 10000000000)))))
(let f ((l (reverse (search-for-prime '(100000000000)))))
(cond ((not (null? l))
(let ff ((prime-list (car l)))
(cond ((null? prime-list) (f (cdr l)))
(else
(timed-prime-test (car prime-list))
(ff (cdr prime-list)))))))))
(define (search-for-prime l)
(let f ((l l) (result '()))
(cond ((null? l) result)
(else
(f (cdr l)
(let ff ((n (car l)) (r result) (primes '()))
(if (= (length primes) 3)
(cons primes r)
(cond ((prime? n) (ff (- n 1) r (append primes (cons n '()))))
(else (ff (- n 1) r primes))))))))))12 桁から前に行ってみた。実行結果は以下。
guile> (test-timed-prime-test) 99999999977 *** 180 99999999947 *** 180 99999999943 *** 179 guile>
えらい時間かかりましたがな。しかも普通に加算したナニよりも遅いし。だからオーダは桁全体での処理時間の平均を取らないと駄目、という事なのか。
サンプルが悪い、という結論にしようとしているんですがダウトですか?? (汗
# トータルで 50% の短縮、っていう事実を、なんて言われると微妙やっさ。
Fermat テストについて
問題 1.24 をやってみよう、と思い実装したのですが
ある n について十分な回数テストを行ない、n が常に合格すれば、素数性のテストの過つ確立はいくらでも小さくなるといいたい。
とあり、十分な回数とは一体何回なのか分からんぞ。
って、よくよく考えると fast-prime? と prime? の差って_fermat-test を実行する回数_と_対象データの桁数_だな。fast-prime? の処理時間は処理する数値の桁数マターではなくって、fermat-test の実行回数が計算量になるはず。ってコトで試験を。
以下。(ちなみに fast-prime? に必要な手続きは定義済みが前提)
guile> (define (start-prime-test n start-time)
;; (if (prime? n)
(if (fast-prime? n 100000)
(report-prime (- (get-internal-real-time) start-time))
(newline)))
guile> (test-timed-prime-test)
10000019 *** 3331
10000079 *** 3424
10000103 *** 3662
10000000019 *** 4959
10000000033 *** 4806
10000000061 *** 5024
guile> (define (start-prime-test n start-time)
;; (if (prime? n)
(if (fast-prime? n 100)
(report-prime (- (get-internal-real-time) start-time))
(newline)))
guile> (test-timed-prime-test)
10000019 *** 4
10000079 *** 4
10000103 *** 3
10000000019 *** 5
10000000033 *** 5
10000000061 *** 5
guile> ダウトかなぁ。桁数が大きい方が若干処理に時間がかってる、というあたりが微妙だけど、どうなんでしょうか。一応 fermat-test の実行回数に比例はしてるよな。
備忘録まで。log2 1000 は約 10 との事。(とほほほ
ここにて以下のような定義を見つける
guile> (define (log2 x)
(define (log2-in x n)
(if (< x (expt 2 n))
(- n 1)
(log2-in x (+ n 1))))
(log2-in x 1))
guile> (log2 1000)
9
guile>うーん ... (今イチ中身を理解していない)
大体、expmod の中身がきちんと追っ掛けきれてない部分があるんで上記類推はダウトの可能性が高いな。再度要検討、という事にしておきます。
# ってか、問題 1.25 以降は fermat test な話題だな。
今日は
ダウト多そう (鬱
