SICP - Solution: Exercise 1.24
October 17, 2018
Exercise 1.24 #
Modify the
timed-prime-test
procedure of Exercise 1.22 to usefast-prime?
(the Fermat method), and test each of the 12 primes you found in that exercise. Since the Fermat test has ${\mathrm\Theta(\log n)}$ growth, how would you expect the time to test primes near 1,000,000 to compare with the time needed to test primes near 1000? Do your data bear this out? Can you explain any discrepancy you find?
Solution #
(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)))
I choosed to run each test on 100 random numbers, but this is somewhat a guessed value:
(define (start-prime-test n start-time)
(if (fast-prime? n 100)
(report-prime (- (runtime) start-time))
"nothing"))
Here too, in order to increase precision of the execution time measurement, all computation are run 1000 times on each prime number for each of the algorithm.
I ran in a few issues with the random number generator for the largest prime in my table. I just removed them as it doesn’t change the conclusion.
DrRacket #
log(prime) | prime | time prime? (µs) | time fast-prime? (µs) |
---|---|---|---|
3 | 1,009 | 2.8029 | 175.80 |
3 | 1,013 | 2.3579 | 160.85 |
3 | 1,019 | 2.2888 | 179.21 |
4 | 10,007 | 8.1271 | 218.31 |
4 | 10,009 | 7.7409 | 193.58 |
4 | 10,037 | 7.6669 | 241.30 |
5 | 100,003 | 25.369 | 238.16 |
5 | 100,019 | 24.364 | 279.69 |
5 | 100,043 | 24.239 | 240.71 |
6 | 1,000,003 | 76.642 | 388.47 |
6 | 1,000,033 | 91.104 | 277.81 |
6 | 1,000,037 | 83.062 | 304.60 |
7 | 10,000,019 | 245.59 | 364.91 |
7 | 10,000,079 | 253.24 | 372.02 |
7 | 10,000,103 | 264.88 | 358.31 |
8 | 100,000,007 | 855.93 | 386.96 |
8 | 100,000,037 | 974.68 | 392.14 |
8 | 100,000,039 | 829.26 | 401.62 |
9 | 1,000,000,007 | 2588.9 | 438.92 |
9 | 1,000,000,009 | 2728.9 | 425.29 |
9 | 1,000,000,021 | 2848.4 | 455.42 |
Which can be summarized:
log(prime) | average time prime? (µs) |
delta for 10x (µs) | average time fast-prime? (µs) |
delta for 10x (µs) |
---|---|---|---|---|
3 | 2,4832 | 171,95 | ||
4 | 7,8450 | 5,3618 | 217,73 | 45,7 |
5 | 24,658 | 16,813 | 252,85 | 35,1 |
6 | 83,603 | 58,945 | 323,63 | 70,7 |
7 | 254,57 | 170,97 | 365,08 | 41,4 |
8 | 886,62 | 632,04 | 393,57 | 28,4 |
9 | 2722,1 | 1835,5 | 439,88 | 46,3 |
Chicken Scheme (compiled) #
log(prime) | prime | time prime? (µs) | time fast-prime? (µs) |
---|---|---|---|
3 | 1,009 | 4.0 | 172.0 |
3 | 1,013 | 3.0 | 180.0 |
3 | 1,019 | 4.0 | 193.0 |
4 | 10,007 | 11.0 | 221.0 |
4 | 10,009 | 13.0 | 218.0 |
4 | 10,037 | 10.0 | 224.0 |
5 | 100,003 | 35.0 | 256.0 |
5 | 100,019 | 35.0 | 261.0 |
5 | 100,043 | 38.0 | 276.0 |
6 | 1,000,003 | 113.0 | 297.0 |
6 | 1,000,033 | 111.0 | 296.0 |
6 | 1,000,037 | 114.0 | 311.0 |
7 | 10,000,019 | 353.0 | 355.0 |
7 | 10,000,079 | 355.0 | 381.0 |
7 | 10,000,103 | 362.0 | 384.0 |
8 | 100,000,007 | 1157.0 | 435.0 |
8 | 100,000,037 | 1126.0 | 444.0 |
8 | 100,000,039 | 1126.0 | 450.0 |
9 | 1,000,000,007 | 3516.0 | 462.0 |
9 | 1,000,000,009 | 3744.0 | 477.0 |
9 | 1,000,000,021 | 3641.0 | 499.0 |
Which can be summarized:
log(prime) | average time prime? (µs) |
time multiplication for 10x | average time fast-prime? (µs) |
time increases for 10x (µs) |
---|---|---|---|---|
3 | 3,67 | 181,67 | ||
4 | 11,33 | 3,09 | 221 | 39,3 |
5 | 36 | 3,18 | 264,33 | 43,3 |
6 | 112,67 | 3,13 | 301,33 | 37,0 |
7 | 356,67 | 3,17 | 373,33 | 72,0 |
8 | 1136,33 | 3,19 | 443 | 69,7 |
9 | 3633,67 | 3,20 | 479,33 | 36,3 |
Conclusion #
When the size of prime
is 10 times larger, prime?
require 3 times more computation.
When the size of prime
is 10 times larger, fast-prime?
require a constant increase of 50µs. ${\mathrm\Theta(\log n)}$ growth means that when the prime are ten times larger, the time will increase by a constant amount ${\log(100)-\log(10)=1}$. This is quite clear here.
Although that for smaller number prime?
is faster, fast-prime?
become much faster with larger and larger prime.