開発環境
計算機プログラムの構造と解釈[第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.28.を取り組んでみる。
その他参考書籍
問題1.28.
コード(Emacs)
(begin (newline) (load "procedures.scm") (define primes '(1009 1013 1019 1000003 1000033 1000037)) (define carnichael-numbers '(561 1105 1729 2465 2821 6601)) (define (expmod base exp m) (if (= exp 0) 1 (if (even? exp) ((lambda () (define t1 (expmod base (/ exp 2) m)) (define t2 (square t1)) (if (and (not (= t1 1)) (not (= t1 (- m 1))) (= (remainder t2 m) 1)) 0 (remainder t2 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 (miller-rabin-test n) (define (try-it a) (= (expmod a (- n 1) n) 1)) (try-it (+ 1 (random (- n 1))))) (define (fast-prime? n times) (if (= times 0) #t (if (miller-rabin-test n) (fast-prime? n (- times 1)) #f))) (for-each (lambda (n) (display n) (display ": ") (display (fast-prime? n 1)) (newline)) (append primes carnichael-numbers)) (newline) 'done)
入出力結果(Terminal(kscheme), REPL(Read, Eval, Print, Loop))
$ ksi < sample28.scm ksi> 1009: #t 1013: #t 1019: #t 1000003: #t 1000033: #t 1000037: #t 561: #f 1105: #f 1729: #f 2465: #f 2821: #f 6601: #f => done ksi> $
0 コメント:
コメントを投稿