計算機プログラムの構造と解釈 第二版 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)