問題1.23

素数計算を高速化し、そのパフォーマンスを測定せよ

nextを使い高速化したバージョン

(define (prime? n)
  (= n (smallest-divisor 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 (next test-divisor)))))

(define (next val)
  (if (= val 2)
      3
      (+ val 2)))

結果は以下の通り

素数	スコア	高速化前	変化率
1009	32	62	0.52
1013	47	63	0.75
1019	46	62	0.74
10007	109	171	0.64
10009	125	172	0.73
10037	94	172	0.55
100003	328	547	0.60
100019	343	547	0.63
100043	328	547	0.60
1000003	1062	1735	0.61
1000033	1063	1734	0.61
1000037	1078	1719	0.63

大体、改良前の状態と比べて1.6倍位早くなっている。
予想通り2倍にならないのは、

1. 関数コール
2. if文

等のオーバーヘッドのためだと思われる。