開発環境
計算機プログラムの構造と解釈[第2版](ハロルド エイブルソン (著)、ジュリー サスマン (著)、ジェラルド・ジェイ サスマン (著)、Harold Abelson (原著)、Julie Sussman (原著)、Gerald Jay Sussman (原著)、和田 英一 (翻訳)、翔泳社、原著: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の第1章(手続きによる抽象の構築)、1.2(手続きとその生成するプロセス)、1.2.6(例: 素数性のテスト)、問題1.24.を取り組んでみる。
その他参考書籍
問題1.24.
コード(Emacs)
(begin
(newline)
(load "procedures.scm")
(define nums '(1000 1000000))
(define count 0)
(define (expmod base exp m)
(if (= exp 0)
1
(if (even? exp)
(remainder (square (expmod base (/ exp 2) m)) m)
(remainder (* base (expmod base (- exp 1) m)) m))))
(define (fermat-test n)
(define (try-it a)
(= (expmod a n n) a))
(try-it (+ 1 (random (- n 1)))))
(define (fast-prime? n times)
(if (= times 0)
#t
(if (fermat-test n)
(fast-prime? n (- times 1))
#f)))
(define (timed-prime-test n)
(newline)
(display n)
(start-prime-test n (current-second)))
(define (start-prime-test n start-time)
(if (fast-prime? n 10)
((lambda ()
(set! count (+ count 1))
(report-prime (- (current-second) start-time))))))
(define (report-prime elapsed-time)
(display " *** ")
(display elapsed-time))
(define (iter n)
(if (not (= count 3))
((lambda ()
(timed-prime-test n)
(iter (+ n 1))))))
;; log 1000000 / log 1000 = 2 で 2倍くらいと予想。
;; 確率的方法だから、試行回数を変えると結果も違ってきそう
(for-each (lambda (n)
(set! count 0)
(iter n))
nums)
(newline)
'done)
入出力結果(Terminal(kscheme), REPL(Read, Eval, Print, Loop))
$ ksi < sample24.scm ksi> 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 *** 0.7354819774627686 1010 1011 1012 1013 *** 0.794813871383667 1014 1015 1016 1017 1018 1019 *** 1.073212146759033 1000000 1000001 1000002 1000003 *** 1.887098073959351 1000004 1000005 1000006 1000007 1000008 1000009 1000010 1000011 1000012 1000013 1000014 1000015 1000016 1000017 1000018 1000019 1000020 1000021 1000022 1000023 1000024 1000025 1000026 1000027 1000028 1000029 1000030 1000031 1000032 1000033 *** 1.422859907150269 1000034 1000035 1000036 1000037 *** 1.306676864624023 => done ksi> $
0 コメント:
コメントを投稿