1 665c255d 2023-08-04 jrmu ;; (define (expmod base exp m)
2 665c255d 2023-08-04 jrmu ;; (cond ((= exp 0) 1)
3 665c255d 2023-08-04 jrmu ;; ((even? exp)
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.23. The smallest-divisor procedure shown at the start of this section does lots of needless testing: After it checks to see if the number is divisible by 2 there is no point in checking to see if it is divisible by any larger even numbers. This suggests that the values used for test-divisor should not be 2, 3, 4, 5, 6, ..., but rather 2, 3, 5, 7, 9, .... To implement this change, define a procedure next that returns 3 if its input is equal to 2 and otherwise returns its input plus 2. Modify the smallest-divisor procedure to use (next test-divisor) instead of (+ test-divisor 1). With timed-prime-test incorporating this modified version of smallest-divisor, run the test for each of the 12 primes found in exercise 1.22. Since this modification halves the number of test steps, you should expect it to run about twice as fast. Is this expectation confirmed? If not, what is the observed ratio of the speeds of the two algorithms, and how do you explain the fact that it is different from 2?
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)
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 (timed-prime-test n)
43 665c255d 2023-08-04 jrmu (start-prime-test n (runtime)))
44 665c255d 2023-08-04 jrmu (define (start-prime-test n start-time)
45 665c255d 2023-08-04 jrmu (if (prime? n)
46 665c255d 2023-08-04 jrmu (report-prime (- (runtime) start-time))))
47 665c255d 2023-08-04 jrmu (define (report-prime elapsed-time)
48 665c255d 2023-08-04 jrmu (display " *** ")
49 665c255d 2023-08-04 jrmu (display elapsed-time))
51 665c255d 2023-08-04 jrmu (define (search-for-primes lower upper)
52 665c255d 2023-08-04 jrmu (cond ((even? lower) (search-for-primes (+ lower 1) upper))
53 665c255d 2023-08-04 jrmu ((< lower upper) (begin (timed-prime-test lower)
54 665c255d 2023-08-04 jrmu (search-for-primes (+ lower 2) upper)))
55 665c255d 2023-08-04 jrmu (else (newline)
56 665c255d 2023-08-04 jrmu (display " *** Finished *** "))))
59 665c255d 2023-08-04 jrmu (search-for-primes 100000001 100000099)
60 665c255d 2023-08-04 jrmu (search-for-primes 1000000001 1000000099)
61 665c255d 2023-08-04 jrmu (search-for-primes 10000000001 10000000099)
62 665c255d 2023-08-04 jrmu (search-for-primes 100000000001 100000000099)
63 665c255d 2023-08-04 jrmu (search-for-primes 1000000000001 1000000000099)
64 665c255d 2023-08-04 jrmu (search-for-primes 10000000000001 10000000000099)
65 665c255d 2023-08-04 jrmu (search-for-primes 100000000000001 100000000000099)
67 665c255d 2023-08-04 jrmu ;; see spreadsheet ex1-23.ods for results
68 665c255d 2023-08-04 jrmu ;; Not quite half, but close enough. This is due to introducing an extra computation at each step due to having to evaluate one extra (next-divisor test-divisor) with each call on the procedure
