計算機プログラムの構造と解釈 第二版 P29 問題1.24
Fermat法を利用してのprime-test
ちゃんと、θ(log n)な感じの計算量増加。
底を10とすると、nが100倍されても、計算量が2倍ってやつ。
nが1000倍なら計算量は3倍。いけてます。
goucheだからかわかんないけど、教科書のFermat法の実装を使うだけだとエラーが出る。何でかっていうと、trueとfalseっていうのがダメだった。
なので、trueは#t、falseは#fでやると通る。
計算時間を調べるだけでもだいたい傾向はわかる。
問題1.23と比較するとさらに熱い!!
#!/usr/local/bin/gosh ;; -*- coding: utf-8 -*- (use ggc.debug.trace) (use math.mt-random) ;;random;;;;;;;;;;;;;;;;;;;;;; (define mt (make <mersenne-twister> :seed (sys-time))) (define (random n) (mt-random-integer mt n)) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;runtime;;;;;;;;;;;;;;;;;;;;;; (define (runtime) (use srfi-11) (let-values (((a b) (sys-gettimeofday))) (+ 1000000 b))) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;1-21;;;;;;;;;;;;;;;;;;;;;;;;; (define (square n) (* n n)) (define (smallest-divisor n) (find-divisor n 2)) (define (find-divisor n test-divisor) (cond ((> (square test-divisor) n) n) ((divides? test-divisor n) test-divisor) (else (find-divisor n (+ test-divisor 1))))) (define (divides? a b) (= (remainder b a) 0)) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;P28 - P29;;;;;;;;;;;;;;;;;;;;;;;;; (define (expmod base exp m) (cond ((= exp 0) 1) ((even? exp) (remainder (square (expmod base (/ exp 2) m)) m)) (else (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) (cond ((= times 0) #t) ((fermat-test n) (fast-prime? n (- times 1))) (else #f))) (define (prime? n) (fast-prime? n 5)) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (define (timed-prime-test n) (newline) (display n) (start-prime-test n (runtime))) (define (start-prime-test n start-time) (if (prime? n) (report-prime (- (runtime) start-time)))) (define (report-prime elapsed-time) (display " *** ") (display elapsed-time)) (define (search-for-primes-iter num counter) (cond ((= counter 3)) ((prime? num) (print num) (search-for-primes-iter (+ num 2) (+ counter 1))) (else (search-for-primes-iter (+ num 2) counter)))) (define (search-for-primes num) (cond ((divides? 2 num) (search-for-primes-iter (+ num 1) 0)) (else (search-for-primes-iter num 0)))) ;; main (define (main args) (search-for-primes 1000) (search-for-primes 10000) (search-for-primes 100000) (search-for-primes 1000000) (search-for-primes 10000000) (search-for-primes 100000000) (search-for-primes 1000000000) (search-for-primes 10000000000) (search-for-primes 100000000000) (timed-prime-test 1009) (timed-prime-test 1013) (timed-prime-test 1019) (timed-prime-test 10007) (timed-prime-test 10009) (timed-prime-test 10037) (timed-prime-test 100003) (timed-prime-test 100019) (timed-prime-test 100043) (timed-prime-test 1000003) (timed-prime-test 1000033) (timed-prime-test 1000037) (timed-prime-test 10000019) (timed-prime-test 10000079) (timed-prime-test 10000103) (timed-prime-test 100000007) (timed-prime-test 100000037) (timed-prime-test 100000039) (timed-prime-test 1000000007) (timed-prime-test 1000000009) (timed-prime-test 1000000021) (timed-prime-test 10000000019) (timed-prime-test 10000000033) (timed-prime-test 10000000061) (timed-prime-test 100000000003) (timed-prime-test 100000000019) (timed-prime-test 100000000057) (newline) 0)