<< Previous exercise (1.23) | sicp-solutions | Next exercise (1.25) >>
This exercise is based on sicp-ex-1.22. Please read the notes therein.
;; ex 1.24 (define (square x) (* x x)) (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) true) ((fermat-test n) (fast-prime? n (- times 1))) (else false))) (define (prime? n) ; Perform the test how many times? ; Use 100 as an arbitrary value. (fast-prime? n 100)) (define (timed-prime-test n) (start-prime-test n (runtime))) (define (start-prime-test n start-time) (if (prime? n) (report-prime n (- (runtime) start-time)))) (define (report-prime n elapsed-time) (newline) (display n) (display " *** ") (display elapsed-time)) (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) ; See comments in exercise 1.22 (newline) (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) (timed-prime-test 1000000000039) (timed-prime-test 1000000000061) (timed-prime-test 1000000000063)
The output produced by the above code is:
1009 *** .01 1013 *** 0. 1019 *** 9.999999999999998e-3 10007 *** 0. 10009 *** 1.0000000000000002e-2 10037 *** 1.0000000000000002e-2 100003 *** 9.999999999999995e-3 100019 *** 1.0000000000000009e-2 100043 *** 9.999999999999995e-3 1000003 *** 9.999999999999995e-3 1000033 *** 1.0000000000000009e-2 1000037 *** .01999999999999999 1000000007 *** 1.0000000000000009e-2 1000000009 *** .01999999999999999 1000000021 *** 2.0000000000000018e-2 10000000019 *** .01999999999999999 10000000033 *** 1.0000000000000009e-2 10000000061 *** .01999999999999999 100000000003 *** .03 100000000019 *** 2.0000000000000018e-2 100000000057 *** 1.9999999999999962e-2 1000000000039 *** 3.0000000000000027e-2 1000000000061 *** 2.0000000000000018e-2 1000000000063 *** .02999999999999997
From the collected timing data, we can observe that testing a number with twice as many digits (1e12 vs. 1e6) is roughly twice as slow. This supports the theory of logarithmic growth.
[torinmr]]: I tested this using much larger numbers (50-200 digits) and obtained slightly different results:
45 digits => 0.04 seconds 90 digits => 0.1 seconds 135 digits => 0.18 seconds 180 digits => 0.27 seconds
If the function ran in logarithmic time, we would expect running time to be linear in the number of digits, but the growth is faster than that. This is probably because performing primitive operations on sufficiently large numbers is not constant time, but grows with the size of the number.
Since fermat-test uses a random number, it's possible that the number we use when testing 1,000,000 is not 1000 times larger than the number we use when testing 1000. Hence the difference in runtime.
There are limits on the random procedure in some Scheme implementations (e.g. Racket) preventing fast-prime from reaching values large enough to show non-zero timings on modern computers.
To avoid this in DrRacket add: (#%require (lib "27.ss" "srfi")) to gain access to the random-integer procedure.
Truly massive numbers are needed on modern machines (e.g 10^156 and 10^312 in my case). My observed ratios were 2.7-3.4, most likely because operations on large integers (above the normal 32/64-bit limit) are not constant in time, but functions of the number's size*, as mentioned by torinmr.
*This is due to larger numbers being stored as a n-tuple of 32/64-bit numbers, with n increasing as they grow in size.