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 *** "))))
63 665c255d 2023-08-04 jrmu (search-for-primes 100000000000001 100000000000099)
64 665c255d 2023-08-04 jrmu (search-for-primes 1000000000000001 1000000000000099)
65 665c255d 2023-08-04 jrmu (search-for-primes 10000000000000001 10000000000000099)
66 665c255d 2023-08-04 jrmu (search-for-primes 100000000000000001 100000000000000099)
67 665c255d 2023-08-04 jrmu (search-for-primes 1000000000000000001 1000000000000000099)
68 665c255d 2023-08-04 jrmu (search-for-primes 10000000000000000001 10000000000000000099)
71 665c255d 2023-08-04 jrmu ;;can't even test due to small numbers being too fast, large numbers being too large to be represented
