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))
22 665c255d 2023-08-04 jrmu (define (prime? n)
23 665c255d 2023-08-04 jrmu (let ((times-to-test 10))
24 665c255d 2023-08-04 jrmu (fast-prime? n times-to-test)))
26 665c255d 2023-08-04 jrmu (define (timed-prime-test n)
29 665c255d 2023-08-04 jrmu (start-prime-test n (runtime)))
30 665c255d 2023-08-04 jrmu (define (start-prime-test n start-time)
31 665c255d 2023-08-04 jrmu (if (prime? n)
32 665c255d 2023-08-04 jrmu (report-prime (- (runtime) start-time))))
33 665c255d 2023-08-04 jrmu (define (report-prime elapsed-time)
34 665c255d 2023-08-04 jrmu (display " *** ")
35 665c255d 2023-08-04 jrmu (display elapsed-time))
37 665c255d 2023-08-04 jrmu (define (search-for-primes lower upper)
38 665c255d 2023-08-04 jrmu (cond ((even? lower) (search-for-primes (+ lower 1) upper))
39 665c255d 2023-08-04 jrmu ((< lower upper) (begin (timed-prime-test lower)
40 665c255d 2023-08-04 jrmu (search-for-primes (+ lower 2) upper)))
41 665c255d 2023-08-04 jrmu (else (newline)
42 665c255d 2023-08-04 jrmu (display " *** Finished *** "))))
44 665c255d 2023-08-04 jrmu (search-for-primes 100000000000001 100000000000099)
45 665c255d 2023-08-04 jrmu (search-for-primes 1000000000000001 1000000000000099)
46 665c255d 2023-08-04 jrmu (search-for-primes 10000000000000001 10000000000000099)
47 665c255d 2023-08-04 jrmu (search-for-primes 100000000000000001 100000000000000099)
48 665c255d 2023-08-04 jrmu (search-for-primes 1000000000000000001 1000000000000000099)
49 665c255d 2023-08-04 jrmu (search-for-primes 10000000000000000001 10000000000000000099)
51 665c255d 2023-08-04 jrmu ;; Exercise 1.26. Louis Reasoner is having great difficulty doing exercise 1.24. His fast-prime? test seems to run more slowly than his prime? test. Louis calls his friend Eva Lu Ator over to help. When they examine Louis's code, they find that he has rewritten the expmod procedure to use an explicit multiplication, rather than calling square:
53 665c255d 2023-08-04 jrmu (define (expmod base exp m)
54 665c255d 2023-08-04 jrmu (cond ((= exp 0) 1)
55 665c255d 2023-08-04 jrmu ((even? exp)
56 665c255d 2023-08-04 jrmu (remainder (* (expmod base (/ exp 2) m)
57 665c255d 2023-08-04 jrmu (expmod base (/ exp 2) m))
60 665c255d 2023-08-04 jrmu (remainder (* base (expmod base (- exp 1) m))
63 665c255d 2023-08-04 jrmu ;;``I don't see what difference that could make,'' says Louis. ``I do.'' says Eva. ``By writing the procedure like that, you have transformed the (log n) process into a (n) process.'' Explain.
65 665c255d 2023-08-04 jrmu ;; Every time exp = 2, we have to calculate (expmod base (/ exp 2) m) twice instead of once. But this ultimately ends up creating lots more calls because this occurs at each procedure call where exp = 2. In total, there will be 'exp' number of alls rather than the original roughly log(exp) number of calls.
67 665c255d 2023-08-04 jrmu ;; We used to have a linear(??) recursion at each step but now have a tree(??) recursion. It used to be O(log) but because it increase exponentially, it is back to the order of exp.
