1 665c255d 2023-08-04 jrmu (define (expmod base exp m)
2 665c255d 2023-08-04 jrmu (cond ((= exp 0) 1)
4 665c255d 2023-08-04 jrmu (remainder (square (expmod base (/ exp 2) m)) m))
5 665c255d 2023-08-04 jrmu (else (remainder (* base (expmod base (- exp 1) m)) m))))
7 665c255d 2023-08-04 jrmu (define (fermat-test n)
8 665c255d 2023-08-04 jrmu (define (try-it a)
9 665c255d 2023-08-04 jrmu (= (expmod a n n) a))
10 665c255d 2023-08-04 jrmu (try-it (+ 1 (random (- n 1)))))
12 665c255d 2023-08-04 jrmu (define (fast-prime? n times)
13 665c255d 2023-08-04 jrmu (cond ((= times 0) true)
14 665c255d 2023-08-04 jrmu ((fermat-test n) (fast-prime? n (- times 1)))
15 665c255d 2023-08-04 jrmu (else false)))
17 665c255d 2023-08-04 jrmu ;; (define (test-case actual expected)
18 665c255d 2023-08-04 jrmu ;; (load-option 'format)
19 665c255d 2023-08-04 jrmu ;; (newline)
20 665c255d 2023-08-04 jrmu ;; (format #t "Actual: ~A Expected: ~A" actual expected))
23 665c255d 2023-08-04 jrmu ;; Exercise 1.24. Modify the timed-prime-test procedure of exercise 1.22 to use fast-prime? (the Fermat method), and test each of the 12 primes you found in that exercise. Since the Fermat test has (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?
25 665c255d 2023-08-04 jrmu ;; (define (smallest-divisor n)
26 665c255d 2023-08-04 jrmu ;; (find-divisor n 2))
27 665c255d 2023-08-04 jrmu ;; (define (find-divisor n test-divisor)
28 665c255d 2023-08-04 jrmu ;; (define (next-divisor n)
29 665c255d 2023-08-04 jrmu ;; (if (= n 2)
31 665c255d 2023-08-04 jrmu ;; (+ n 2)))
32 665c255d 2023-08-04 jrmu ;; (cond ((> (square test-divisor) n) n)
33 665c255d 2023-08-04 jrmu ;; ((divides? test-divisor n) test-divisor)
34 665c255d 2023-08-04 jrmu ;; (else (find-divisor n (next-divisor test-divisor)))))
35 665c255d 2023-08-04 jrmu ;; (define (divides? a b)
36 665c255d 2023-08-04 jrmu ;; (= (remainder b a) 0))
37 665c255d 2023-08-04 jrmu ;; (define (prime? n)
38 665c255d 2023-08-04 jrmu ;; (= n (smallest-divisor n)))
40 665c255d 2023-08-04 jrmu (define (prime? n)
41 665c255d 2023-08-04 jrmu (let ((times-to-test 10))
42 665c255d 2023-08-04 jrmu (fast-prime? n times-to-test)))
44 665c255d 2023-08-04 jrmu (define (timed-prime-test n)
47 665c255d 2023-08-04 jrmu (start-prime-test n (runtime)))
48 665c255d 2023-08-04 jrmu (define (start-prime-test n start-time)
49 665c255d 2023-08-04 jrmu (if (prime? n)
50 665c255d 2023-08-04 jrmu (report-prime (- (runtime) start-time))))
51 665c255d 2023-08-04 jrmu (define (report-prime elapsed-time)
52 665c255d 2023-08-04 jrmu (display " *** ")
53 665c255d 2023-08-04 jrmu (display elapsed-time))
55 665c255d 2023-08-04 jrmu (define (search-for-primes lower upper)
56 665c255d 2023-08-04 jrmu (cond ((even? lower) (search-for-primes (+ lower 1) upper))
57 665c255d 2023-08-04 jrmu ((< lower upper) (begin (timed-prime-test lower)
58 665c255d 2023-08-04 jrmu (search-for-primes (+ lower 2) upper)))
59 665c255d 2023-08-04 jrmu (else (newline)
60 665c255d 2023-08-04 jrmu (display " *** Finished *** "))))
62 665c255d 2023-08-04 jrmu (search-for-primes 100000000000001 100000000000099)
63 665c255d 2023-08-04 jrmu (search-for-primes 1000000000000001 1000000000000099)
64 665c255d 2023-08-04 jrmu (search-for-primes 10000000000000001 10000000000000099)
65 665c255d 2023-08-04 jrmu (search-for-primes 100000000000000001 100000000000000099)
66 665c255d 2023-08-04 jrmu (search-for-primes 1000000000000000001 1000000000000000099)
67 665c255d 2023-08-04 jrmu (search-for-primes 10000000000000000001 10000000000000000099)
69 665c255d 2023-08-04 jrmu ;; Exercise 1.25. Alyssa P. Hacker complains that we went to a lot of extra work in writing expmod. After all, she says, since we already know how to compute exponentials, we could have simply written
71 665c255d 2023-08-04 jrmu ;; (define (expmod base exp m)
72 665c255d 2023-08-04 jrmu ;; (remainder (fast-expt base exp) m))
74 665c255d 2023-08-04 jrmu ;; Is she correct? Would this procedure serve as well for our fast prime tester? Explain.
76 665c255d 2023-08-04 jrmu (define (expmod base exp m)
77 665c255d 2023-08-04 jrmu (remainder (fast-expt base exp) m))
79 665c255d 2023-08-04 jrmu (define (expmod base exp m)
80 665c255d 2023-08-04 jrmu (cond ((= exp 0) 1)
81 665c255d 2023-08-04 jrmu ((even? exp)
82 665c255d 2023-08-04 jrmu (remainder (square (expmod base (/ exp 2) m)) m))
83 665c255d 2023-08-04 jrmu (else (remainder (* base (expmod base (- exp 1) m)) m))))
85 665c255d 2023-08-04 jrmu (define (expmod base exp m)
86 665c255d 2023-08-04 jrmu (cond ((= exp 0) 1)
87 665c255d 2023-08-04 jrmu ((even? exp)
88 665c255d 2023-08-04 jrmu (remainder (square (expmod base (/ exp 2) m)) m))
89 665c255d 2023-08-04 jrmu (else (remainder (* base (expmod base (- exp 1) m)) m))))
91 665c255d 2023-08-04 jrmu ;; Calculating exponentials using (fast-expt ...) gets slower and slower since we are calculating absolutely huge exponents (base^10000000... and higher). Doing multiplication requires more steps as the exponents get bigger, which is why using (expmod) is a huge benefit. The actual multiplications are never bigger than m.
