SICP 読み (9)

色々ヤる事あるんですが、なんやかやでまだ勉強ネタに現実トウヒ (を

問題 1.23

実装自体は簡単なんですが、考察が微妙。

(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)))))
	(else (find-divisor n (next test-divisor)))))
(define (divides? a b)
  (= (remainder b a) 0))
(define (next n)
  (if (= n 2)
      3
      (+ n 2)))

(define (prime? n)
  (= n (smallest-divisor n)))

(define (test-timed-prime-test)
  (let f ((l (reverse (search-for-prime '(100000000 1000000000 10000000000)))))
    (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))))))))))

(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (get-internal-real-time)))
(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (get-internal-real-time) start-time))
      (newline)))
(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time)
  (newline))

実行してみた。

guile> (test-timed-prime-test)

100000007 *** 5

100000037 *** 5

100000039 *** 6

1000000007 *** 16

1000000009 *** 17

1000000021 *** 16

10000000019 *** 60

10000000033 *** 58

10000000061 *** 59
guile> 

(+ test-divisor 1) の時の平均処理時間 (って言って良いのかどうか) は

• 9 桁 : 13.3333 (単位時間)
• 11 桁 : 43 (単位時間)
• 13 桁 : 160.6666 (単位時間)

になっている。2 倍よりはもう少し早いな。

ってか、上記の数値が本当に素数かどうかを確認してないぜ (を
処理時間のナニについての事情は別途検討とゆー事にさせて下さい。
;; またスルーかよ、とは言わないで下さひ。