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))))
 6 665c255d 2023-08-04 jrmu 
 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)))))
11 665c255d 2023-08-04 jrmu 
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)))
16 665c255d 2023-08-04 jrmu 
17 665c255d 2023-08-04 jrmu (define (smallest-divisor n)
18 665c255d 2023-08-04 jrmu   (find-divisor n 2))
19 665c255d 2023-08-04 jrmu (define (find-divisor n test-divisor)
20 665c255d 2023-08-04 jrmu   (cond ((> (square test-divisor) n) n)
21 665c255d 2023-08-04 jrmu 	((divides? test-divisor n) test-divisor)
22 665c255d 2023-08-04 jrmu 	(else (find-divisor n (+ test-divisor 1)))))
23 665c255d 2023-08-04 jrmu (define (divides? a b)
24 665c255d 2023-08-04 jrmu   (= (remainder b a) 0))
25 665c255d 2023-08-04 jrmu (define (prime? n)
26 665c255d 2023-08-04 jrmu   (= n (smallest-divisor n)))
27 665c255d 2023-08-04 jrmu 
28 665c255d 2023-08-04 jrmu (define (test-case actual expected)
29 665c255d 2023-08-04 jrmu   (load-option 'format)
30 665c255d 2023-08-04 jrmu   (newline)
31 665c255d 2023-08-04 jrmu   (format #t "Actual: ~A Expected: ~A" actual expected))
32 665c255d 2023-08-04 jrmu 
33 665c255d 2023-08-04 jrmu (define (timed-prime-test n)
34 665c255d 2023-08-04 jrmu   (newline)
35 665c255d 2023-08-04 jrmu   (display n)
36 665c255d 2023-08-04 jrmu   (start-prime-test n (runtime)))
37 665c255d 2023-08-04 jrmu (define (start-prime-test n start-time)
38 665c255d 2023-08-04 jrmu   (if (prime? n)
39 665c255d 2023-08-04 jrmu       (report-prime (- (runtime) start-time))))
40 665c255d 2023-08-04 jrmu (define (report-prime elapsed-time)
41 665c255d 2023-08-04 jrmu   (display " *** ")
42 665c255d 2023-08-04 jrmu   (display elapsed-time))
43 665c255d 2023-08-04 jrmu 
44 665c255d 2023-08-04 jrmu (define (search-for-primes lower upper)
45 665c255d 2023-08-04 jrmu   (cond ((even? lower) (search-for-primes (+ lower 1) upper))
46 665c255d 2023-08-04 jrmu 	((< lower upper) (begin (timed-prime-test lower)
47 665c255d 2023-08-04 jrmu 				(search-for-primes (+ lower 2) upper)))
48 665c255d 2023-08-04 jrmu 	(else (newline)
49 665c255d 2023-08-04 jrmu 	      (display " *** Finished *** "))))
50 665c255d 2023-08-04 jrmu 
51 665c255d 2023-08-04 jrmu (search-for-primes 100000001 100000099)
52 665c255d 2023-08-04 jrmu (search-for-primes 1000000001 1000000099)
53 665c255d 2023-08-04 jrmu (search-for-primes 10000000001 10000000099)
54 665c255d 2023-08-04 jrmu (search-for-primes 100000000001 100000000099)
55 665c255d 2023-08-04 jrmu (search-for-primes 1000000000001 1000000000099)
56 665c255d 2023-08-04 jrmu (search-for-primes 10000000000001 10000000000099)
57 665c255d 2023-08-04 jrmu (search-for-primes 100000000000001 100000000000099)
58 665c255d 2023-08-04 jrmu 
59 665c255d 2023-08-04 jrmu ;; see spreadsheet for results and charts
60 665c255d 2023-08-04 jrmu 
61 665c255d 2023-08-04 jrmu ;; Yes, our timing data perfectly fits the order of growth prediction that R(n) is of the order sqrt(n). So, it seems that our programs do run in time proportional to number of steps required.
62 665c255d 2023-08-04 jrmu