問題1.23

SICP

変更点

(define (next-tester n)
  (if (= n 2)
	  3
	  (+ 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-tester test-divisor)))))

テスト。

  • 1,000

1009 *** 1.8835067749023437e-5
1013 *** 1.8835067749023437e-5
1019 *** 1.9073486328125e-5

  • 10,000

10007 *** 5.0067901611328125e-5
10009 *** 4.982948303222656e-5
10037 *** 4.982948303222656e-5

  • 100,000

100043 *** 1.8596649169921875e-4
100019 *** 1.499652862548828e-4
100003 *** 1.4901161193847656e-4

  • 1,000,000

1000003 *** 4.6706199645996094e-4
1000033 *** 4.570484161376953e-4
1000037 *** 5.970001220703125e-4

前問との比較。

n Conv Improved Ratio
1,000 2.74e-5 1.89e-5 1.45
10,000 5.30e-5 4.99e-5 1.06
100,000 2.40e-4 1.62e-4 1.48
1,000,000 8.44e-4 4.85e-4 1.74

確かに、2倍にはならない。とすると、誤差って何だろう？　テスト数は確かにほぼ半分になってるはずなのだが。