1 (define (expmod base exp m)
2   (cond ((= exp 0) 1)
3 	((even? exp)
4 	 (remainder (square (expmod base (/ exp 2) m)) m))
5 	(else (remainder (* base (expmod base (- exp 1) m)) m))))
6 
7 (define (fermat-test n)
8   (define (try-it a)
9     (= (expmod a n n) a))
10   (try-it (+ 1 (random (- n 1)))))
11 
12 (define (fast-prime? n times)
13   (cond ((= times 0) true)
14 	((fermat-test n) (fast-prime? n (- times 1)))
15 	(else false)))
16 
17 ;; (define (test-case actual expected)
18 ;;   (load-option 'format)
19 ;;   (newline)
20 ;;   (format #t "Actual: ~A Expected: ~A" actual expected))
21 
22 (define (prime? n)
23   (let ((times-to-test 10))
24     (fast-prime? n times-to-test)))
25 
26 (define (timed-prime-test n)
27   (newline)
28   (display n)
29   (start-prime-test n (runtime)))
30 (define (start-prime-test n start-time)
31   (if (prime? n)
32       (report-prime (- (runtime) start-time))))
33 (define (report-prime elapsed-time)
34   (display " *** ")
35   (display elapsed-time))
36 
37 (define (search-for-primes lower upper)
38   (cond ((even? lower) (search-for-primes (+ lower 1) upper))
39 	((< lower upper) (begin (timed-prime-test lower)
40 				(search-for-primes (+ lower 2) upper)))
41 	(else (newline)
42 	      (display " *** Finished *** "))))
43 
44 (search-for-primes 100000000000001 100000000000099)
45 (search-for-primes 1000000000000001 1000000000000099)
46 (search-for-primes 10000000000000001 10000000000000099)
47 (search-for-primes 100000000000000001 100000000000000099)
48 (search-for-primes 1000000000000000001 1000000000000000099)
49 (search-for-primes 10000000000000000001 10000000000000000099)
50 
51 ;; 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:
52 
53 (define (expmod base exp m)
54   (cond ((= exp 0) 1)
55         ((even? exp)
56          (remainder (* (expmod base (/ exp 2) m)
57                        (expmod base (/ exp 2) m))
58                     m))
59         (else
60          (remainder (* base (expmod base (- exp 1) m))
61                     m))))
62 
63 ;;``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. 
64 
65 ;; 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.
66 n
67 ;; 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.