Procedures and the Processes They Generate Exercises

1.2

Linear Recursion and Iteration

Linear recursive process:

(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))

(factorial 6)
=> (* 6 (factorial 5))
=> (* 6 (* 5 (factorial 4)))
=> (* 6 (* 5 (* 4 (factorial 3))))
=> (* 6 (* 5 (* 4 (* 3 (factorial 2)))))
=> (* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1))))))
=> (* 6 (* 5 (* 4 (* 3 (* 2 1)))))
=> (* 6 (* 5 (* 4 (* 3 2))))
=> (* 6 (* 5 (* 4 6)))
=> (* 6 (* 5 24))
=> (* 6 120)
=> 720

Linear iterative process:

(define (factorial n)
  (fact-iter 1 1 n))
(define (fact-iter product counter max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max-count)))

(factorial 6)
=> (fact-iter 1 1 6)
=> (fact-iter 1 2 6)
=> (fact-iter 2 3 6)
=> (fact-iter 6 4 6)
=> (fact-iter 24 5 6)
=> (fact-iter 120 6 6)
=> (fact-iter 720 7 6)
=> 720

Exercise 1.9

(define (inc x) (+ x 1)) 
(define (dec x) (- x 1)) 

(define (r+ a b) 
  (if (= a 0) b (inc (r+ (dec a) b)))) 
  
(define (i+ a b) 
  (if (= a 0) b (i+ (dec a) (inc b))))

r+ generates a recursive process:

(r+ 4 5) 
=> (inc (r+ 3 5)) 
=> (inc (inc (r+ 2 5))) ; expanding 
=> (inc (inc (inc (r+ 1 5)))) 
=> (inc (inc (inc (inc (r+ 0 5))))) ; 4 deferred operations
=> (inc (inc (inc (inc 5)))) 
=> (inc (inc (inc 6))) ; contracting 
=> (inc (inc 7)) 
=> (inc 8) 
=> 9

i+ generates an iterative process:

(i+ 4 5) 
=> (i+ 3 6) 
=> (i+ 2 7) 
=> (i+ 1 8) 
=> (i+ 0 9) 
=> 9

Exercise 1.10

(define (A x y) 
  (cond ((= y 0) 0) 
		((= x 0) (* 2 y)) 
		((= y 1) 2) 
		(else (A (- x 1) 
		         (A x (- y 1)))))) 
(A 1 10) => 1024 
(A 2 4) => 65536 
(A 3 3) => 65536 


(define (f n) (A 0 n)) 
(define (g n) (A 1 n)) 
(define (h n) (A 2 n)) 
(define (k n) (* 5 n n))

(f n) computes $2n$ , since (A 0 n) => (* 2 n).

(g n) computes $2^n$ since (A 1 n) => (A 0 (A 1 (- n 1))) => (f (g (- n 1))).

(h n) computes $^n{2}$ : (A 2 n) => (A 1 (A 2 (- n 1))) => (g (h (- n 1))).

(k n) computes $5n^2$ , as stated in the exercise.

Tree Recursion

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

(fib 6) => 8

(define (fib n)
  (define (iter a b count)
    (if (= count 0)
        b
        (iter (+ a b) a (- count 1))))
  (iter 1 0 n))

(fib 6) => 8

Example: Counting Change

(define (count-change amount)
  (define (cc a n)
    (cond ((< a 0) 0)
          ((= a 0) 1)
          ((= n 0) 0)
          (else (+ (cc a (- n 1))
                   (cc (- a (first-denomination n)) n)))))
  (cc amount 5))

(define (first-denomination kinds-of-coins)
  (vector-ref '#(1 5 10 25 50) (- kinds-of-coins 1)))

(count-change 100) => 292

Exercise 1.11

Recursive process:

(define (f n)
  (if (< n 3)
      n
      (+ (f (- n 1))
         (* 2 (f (- n 2)))
         (* 3 (f (- n 3))))))

(f 5) => 25

Iterative process:

(define (f n)
  (define (iter a b c counter)
    (if (= counter 0)
        a
        (iter b c (+ c (* 2 b) (* 3 a)) (- counter 1))))
  (iter 0 1 2 n))

(f 5) => 25

Exercise 1.12

(define (pascal i j) 
  (if (or (= j 0) (= j i)) 
      1 
      (+ (pascal (- i 1) (- j 1)) 
         (pascal (- i 1) j)))) 

(pascal 3 0) => 1 
(pascal 3 1) => 3 
(pascal 3 2) => 3 
(pascal 3 3) => 1

Exercise 1.13

The constants $φ$ and $ψ$ are the solutions to the golden ration equation $x + 1 = x^2$ :

\phi = \frac{1+\sqrt{5}}{2}, \ \ \ \ \phi = \frac{1-\sqrt{5}}{2}.

The Fibonacci sequence is defined recursively by

\begin{aligned} \operatorname{Fib}(0) &= 0,\newline \operatorname{Fib}(1) &= 1,\newline \operatorname{Fib}(n) &= \operatorname{Fib}(n-1) + \operatorname{Fib}(n-2). \end{aligned}

Lemma. $\operatorname{Fib}(n)$ is equal to $f(n) = \frac{φ^n - ψ^n}{\sqrt{5}}$ .

Proof. First, we will demonstrate three base cases. When $n = 0$ ,

f(0) = \frac{φ^0 - ψ^0}{\sqrt{5}} = \frac{1-1}{\sqrt{5}} = 0

When $n = 1$ ,

f(1)=\frac{φ^1 - ψ^1}{\sqrt{5}} = \frac{\frac{1+\sqrt{5}}{2} - \frac{1-\sqrt{5}}{2}}{\sqrt{5}} = \frac{\frac{2\sqrt{5}}{2}}{\sqrt{5}} = 1

When $n = 2$ ,

\begin{aligned} f(2) &= \frac{φ^2 - ψ^2}{\sqrt{5}} \newline &= \frac{(\frac{1+\sqrt{5}}{2})^2 - (\frac{1-\sqrt{5}}{2})^2}{\sqrt{5}} \newline &= \frac{\frac{(1+\sqrt{5})^2 - (1 - \sqrt{5})^2}{4}}{\sqrt{5}} \newline &= \frac{((1+\sqrt{5}) - (1 - \sqrt{5})) \ ((1+\sqrt{5}) + (1-\sqrt{5}))}{4 \sqrt{5}} \newline &= \frac{(2\sqrt{5})(2)}{4\sqrt{5}} \newline &= 1. \end{aligned}

Now comes the inductive step:

\begin{aligned} f(n-1) + f(n-2) &= \frac{φ^{n-1} - ψ^{n-1}}{\sqrt{5}} + \frac{φ^{n-2} - ψ^{n-2}}{\sqrt{5}} \newline &= \frac{(φ^{n-1} + φ^{n-2}) - (ψ^{n-1} + ψ^{n-2})}{\sqrt{5}} \newline &= \frac{φ^n \ (φ^{-1} + φ^{-2}) - ψ^n \ (ψ^{-1} + ψ^{-2})}{\sqrt{5}} \newline &= \frac{φ^nφ^{-1} \ (1 + φ^{-1}) - ψ^nψ^{-1} \ (1 + ψ^{-1})}{\sqrt{5}} \newline &= \frac{φ^nφ^{-1} \ (φ) - ψ^nψ^{-1} \ (ψ)}{\sqrt{5}} \newline &= \frac{φ^n - ψ^n}{\sqrt{5}} \newline &= f(n). \end{aligned}

By induction, $f(n) = \operatorname{Fib}(n)$ for all $n$ . $\blacksquare$

Theorem. $\operatorname{Fib}(n)$ is the closest integer to $\dfrac{φ^n}{\sqrt{5}}$ , where $φ = \dfrac{1 + \sqrt{5}}{2}$ .

Proof. It suffices to show that the absolute difference is less than one half:

\begin{aligned} \left\lvert \operatorname{Fib}(n) - \frac{φ^n}{\sqrt{5}} \right\rvert &< \frac{1}{2} \newline \left\lvert \frac{φ^n - ψ^n}{\sqrt{5}}-\frac{φ^n}{\sqrt{5}}\right\rvert &< \frac{1}{2} \newline \left\lvert -\frac{ψ^n}{\sqrt{5}}\right\rvert &< \frac{1}{2} \newline \frac{|-ψ^n|}{\sqrt{5}} &< \frac{1}{2} \newline |ψ|^n &< \frac{\sqrt{5}}{2}. \end{aligned}

Since $|ψ| < 0.619 < 1$ , we have $|ψ|^n < 1 < \dfrac{\sqrt{5}}{2}$ for all $n$ . $\blacksquare$

Orders of Growth

Exercise 1.14

Imports: Example: Counting Change count-change

(count-change 11) => 4

Here is the process generated by (count-change 11):

(cc 11 5)
  (cc -39 5) => 0
  (cc 11 4)
    (cc -14 4) => 0
    (cc 11 3)
      (cc 1 3)
        (cc -9 3) => 0
        (cc 1 2)
          (cc -4 2) => 0
          (cc 1 1)
            (cc 0 1) => 1
            (cc 1 0) => 0
      (cc 11 2)
        (cc 6 2)
          (cc 1 2)
            (cc -4 2) => 0
            (cc 1 1)
              (cc 0 1) => 1
              (cc 1 0) => 0
          (cc 6 1)
            (cc 5 1)
              (cc 4 1)
                (cc 3 1)
                  (cc 2 1)
                    (cc 1 1)
                      (cc 0 1) => 1
                      (cc 1 0) => 0
                    (cc 2 0) => 0
                  (cc 3 0) => 0
                (cc 4 0) => 0
              (cc 5 0) => 0
            (cc 6 0) => 0
        (cc 11 1)
          (cc 10 1)
            (cc 9 1)
              (cc 8 1)
                (cc 7 1)
                  (cc 6 1)
                    (cc 5 1)
                      (cc 4 1)
                        (cc 3 1)
                          (cc 2 1)
                            (cc 1 1)
                              (cc 0 1) => 1
                              (cc 1 0) => 0
                            (cc 2 0) => 0
                          (cc 3 0) => 0
                        (cc 4 0) => 0
                      (cc 5 0) => 0
                    (cc 6 0) => 0
                  (cc 7 0) => 0
                (cc 8 0) => 0
              (cc 9 0) => 0
            (cc 10 0) => 0
          (cc 11 0) => 0

Orders of growth:

Steps: $\Theta(n^5)$ because there are 5 types of coins.
Space: $\Theta(n)$ because the maximum depth of the tree grows linearly.

Remember: for a tree-recursive process, space is proportional to the maximum depth of the tree, and the number of steps is the number of leaves.

Exercise 1.15

(define (cube x) (* x x x))
(define (p x) (- (* 3 x) (* 4 (cube x))))
(define (sine theta)
  (if (<= (abs theta) 0.1)
      theta
      (p (sine (/ theta 3.0)))))

a. The procedurepis evaluated five times for (sine 12.15):

(sine 12.15)
~> (p (sine 4.05))
~> (p (p (sine 1.35)))
~> (p (p (p (sine 0.45))))
~> (p (p (p (p (sine 0.15)))))
~> (p (p (p (p (p (sine 0.05)))))) ; five times until theta <= 0.1

b. During the process, p is evaluated $k$ times such that $\theta / 3^k < 0.1$ . Solving for $k$ gives $k = \log10\theta / \log3$ , thus the number of steps for sine grows as $\Theta(\log n)$ . The interpreter must maintain the stack for that number of calls to p, so the space complexity is also $\Theta(\log n)$ .

Exponentiation

Imports: Compound Procedures square

Recursive, naive: $\Theta(n)$ time, $\Theta(n)$ space.

(define (expt b n)
  (if (= n 0)
      1
      (* b (expt b (- n 1)))))

(expt 2 5) => 32

Iterative, naive: $\Theta(n)$ time, $\Theta(1)$ space.

(define (expt b n)
  (define (iter counter prod)
    (if (= counter 0)
        prod
        (iter (- counter 1) (* prod b))))
  (iter n 1))

(expt 2 5) => 32

Recursive, succesive squaring: $\Theta(\log n)$ time, $\Theta(\log n)$ space.

(define (fast-expt b n)
  (cond ((= n 0) 1)
        ((even? n) (square (fast-expt b (/ n 2))))
        (else (* b (fast-expt b (- n 1))))))

(fast-expt 2 5) => 32

Exercise 1.16

Imports: Compound Procedures square

Iterative, successive squaring: $\Theta (\log n)$ time, $\Theta(\log n)$ space.

(define (fast-expt b n)
  (define (iter a b n)
    (cond ((= n 0) a)
          ((even? n) (iter a (square b) (/ n 2)))
          (else (iter (* a b) b (- n 1)))))
  (iter 1 b n))

(fast-expt 2 5) => 32
(fast-expt 2 100) => 1267650600228229401496703205376

Exercise 1.17

Recursive, naive: $\Theta(n)$ time, $\Theta(n)$ space.

(define (* a b)
  (if (= b 0)
      0
      (+ a (* a (- b 1)))))

(* 5 4) => 20

These are taken as primitives:

(define (double x) (+ x x))
(define (halve x) (/ x 2))

Recursive, sucessive doubling: $\Theta(\log n)$ time, $\Theta(\log n)$ space.

(define (fast-* a b)
  (cond ((= b 0) 0)
        ((even? b) (double (fast-* a (halve b))))
        (else (+ a (fast-* a (- b 1))))))

(fast-* 5 4) => 20

Exercise 1.18

Imports: Compound Procedures double halve

Iterative, successive doubling: $\Theta(\log n)$ time, $\Theta(1)$ space.

(define (fast-* a b)
  (define (iter c a b)
    (cond ((= b 0) c)
          ((even? b) (iter c (double a) (halve b)))
          (else (iter (+ c a) a (- b 1)))))
  (iter 0 a b))
x
(fast-* 5 4) => 20

Exercise 1.19

Let $T_{pq}(a,b) = (bq+aq+ap,bp+aq).$ Applying $T_{pq}$ twice gives

\begin{aligned} & \ \ \ \ \ \ T_{pq}(T_{pq}(a,b)) \\ &= \ T_{pq}(bq+aq+ap,bp+aq) \\ &= \ ((bp +aq)q + (bq + aq + ap)q + (bq+aq+ap)p), \\ & \ \ \ \ \ \ \ (bp+aq)p + (bq+aq+ap)q)\\ &= \ (bpq + aq^2 + bq(q+p) + aq(q+p) + ap(q+p)), \\ & \ \ \ \ \ \ \ bp^2 + aqp + bq^2 +aq^2 + apq) \\ &=(b-q + aq^2 +bq^2 + bpq + aq^2 + apq+ apq +ap^2, \\ & \ \ \ \ \ \ \ bp^2 +apq+bq^2 + aq^2 + apq) \\ &= \ (b(q^2 + 2pq) + a(q^2 +2pq) + a(p^2 + q^2), \\ & \ \ \ \ \ \ \ b(p^2+q^2)+a(q^2 + 2pq)) \\ &= \ T_{p'q'}(a,b) \end{aligned}

where $p' = p^2 + q^2$ and $q' = q^2 + 2pq$ .

Using this, we can implement fib with $\Theta(\log n)$ time complexity:

(define (fib n)
  (define (iter a b p q count)
    (cond ((= count 0) b)
          ((even? count)
           (iter a
                 b
                 (+ (* p p) (* q q))
                 (+ (* q q) (* 2 p q))
                 (/ count 2)))
          (else (iter (+ (* b q) (* a q) (* a p))
                      (+ (* b p) (* a q))
                      p
                      q
                      (- count 1)))))
  (iter 1 0 0 1 n))

(fib 6) => 8
(fib 100) => 354224848179261915075

Greatest Common Divisors

Euclid’s Algorithm: $\Theta(\log n)$ time.

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

(gcd 206 40) => 2

## Exercise 1.20
With applicative order, it performs 4 remainder operations.

```scheme
(gcd 206 40)
=> (gcd 40 (remainder 206 40))
=> (gcd 40 6)
=> (gcd 6 (remainder 40 6))
=> (gcd 6 4)
=> (gcd 4 (remainder 6 4))
=> (gcd 4 2)
=> (gcd 2 (remainder 4 2))
=> (gcd 2 0)
=> 2

With normal order, it performs 18 remainder operations. Each b gets evaluated once in the (= b 0) predicate (14 operations). The final a gets evaluated in the end (4 operations). Together, that makes 18.

gcd 206 40)
=> (gcd 40 (remainder 206 40))
=> (gcd (remainder 206 40)
        (remainder 40 (remainder 206 40)))
=> (gcd (remainder 40 (remainder 206 40))
        (remainder (remainder 206 40)
                   (remainder 40 (remainder 206 40))))
=> (gcd (remainder (remainder 206 40)
                   (remainder 40 (remainder 206 40)))
        (remainder (remainder 40 (remainder 206 40))
                   (remainder (remainder 206 40)
                              (remainder 40 (remainder 206 40)))))
=> (remainder (remainder 206 40)
              (remainder 40 (remainder 206 40)))

Example: Testing for Primality

Searching for divisors

Imports: Compound Procedures square

(define (smallest-divisor n) (find-divisor n 2))
(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b) (= (remainder b a) 0))

Trial division: $\Theta(\sqrt{n})$ time.

(define (prime? n)
  (= n (smallest-divisor n)))

(prime? 10) => #f
(prime? 13) => #t

The Fermat Test

Imports: Compound Procedures square, Searching for divisors prime?

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else (remainder (* base (expmod base (- exp 1) m))
                         m))))

(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))

Fermat test: $\Theta(\log n)$ time, probabilistic.

(define (fast-prime? n times)
  (or (= times 0)
      (and (fermat-test n)
           (fast-prime? n (- times 1)))))

(define many-times 10)

The Fermat test only produces false positives on composite numbers, not prime numbers, so we can be certain it will return true for 13.

(fast-prime? 13 many-times) => #t
(fast-prime? 10 many-times) =?> [#f #t] ; correct answer is #f

The first Carmichael number, 561, fools the Fermat test: no matter how many iterations we use, it will always think it’s prime.

(prime? 561) => #f
(fast-prime? 561 many-times) => #t

Exercise 1.21

Imports: Searching for divisors smallest-divisor

(smallest-divisor 199) => 199
(smallest-divisor 1999) => 1999
(smallest-divisor 19999) => 7

Exercise 1.22

Imports: Searching for divisors prime?

define (timed-prime-test p? n)
  (newline)
  (display n)
  (start-prime-test p? n (runtime)))
(define (start-prime-test p? n start-time)
  (when (p? n)
    (report-prime (- (runtime) start-time))))
(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))

(define (search-for-primes p? a b)
  (define (iter a b)
    (when (<= a b)
      (timed-prime-test p? a)
      (iter (+ a 2) b)))
  (iter (if (odd? a) a (+ a 1)) b))

(string-contains?
 (capture-output (search-for-primes prime? 6 10))
 "7 *** ")
=> #t

$A =$ time for 3 primes greater than 1,000.

; 1009 *** 4.792213439941406e-5 
; 1013 *** 4.291534423828125e-5 
; 1019 *** 4.792213439941406e-5

$B =$ time for 3 primes greater than 10,000. $(2.3A < B < 2.8A)$

; 10007 *** 1.1086463928222656e-4 
; 10009 *** 1.1396408081054688e-4 
; 10037 *** 1.2302398681640625e-4

$C =$ time for 3 primes greater than 100,00. $(3.3B < D < 4.1B$

; 100003 *** 4.010200500488281e-4 
; 100019 *** 3.6597251892089844e-4 
; 100043 *** 4.558563232421875e-4

$D =$ time for 3 primes greater than 1,000,000. $2.8C < D < 3.4C$

; 1000003 *** .0013530254364013672 
; 1000033 *** .0011339187622070312 
; 1000037 *** .0013699531555175781

The data bears out the $\Theta(\sqrt{n})$ prediction. The growth between powers of ten gets closer to $\sqrt{10} \approx 3.16$ as $n$ gets larger. This result is compatible with the notion that programs on the machine run in time proportional to the number of steps require for the computation.

Exercise 1.23

Imports: Compound Procedures square, Exercise 1.22 search-for-primes

Trial division, but only testing odd divisors:

(define (prime? n)
  (define (divides? a b)
    (= (remainder b a) 0))
  (define (next n)
    (if (= n 2) 3 (+ n 2)))
  (define (find-divisor n test-divisor)
    (cond ((> (square test-divisor) n) n)
          ((divides? test-divisor n) test-divisor)
          (else (find-divisor n (next test-divisor)))))
  (define (smallest-divisor n)
    (find-divisor n 2))
  (= n (smallest-divisor n)))

(string-contains?
 (capture-output (search-for-primes prime? 6 10))
 "7 *** ")
=> #t

Time for 3 primes greater than 1,000:

; 1009 *** 5.1975250244140625e-5   (1.085x)
; 1013 *** 5.1975250244140625e-5   (1.211x)
; 1019 *** 6.198883056640625e-5    (1.294x)

Time for 3 primes greater than 10,000:

; 10007 *** 1.1491775512695312e-4  (1.037x)
; 10009 *** 1.1801719665527344e-4  (1.036x)
; 10037 *** 1.1897087097167969e-4  (0.967x)

Time for 3 primes greater than 100,000:

; 100003 *** 3.540515899658203e-4  (0.883x)
; 100019 *** 3.490447998046875e-4  (0.954x)
; 100043 *** 3.590583801269531e-4  (0.788x)

Time for 3 primes greater than 1,000,000:

; 1000003 *** .0010960102081298828 (0.810x)
; 1000033 *** .001055002212524414  (0.930x)
; 1000037 *** .0010900497436523438 (0.796x)

The expectation of half time was not confirmed. In fact, this method is actually slower for primes under 10,000. Even for seven-figure primes, it only shaves off 20%. There was probably some error in the measure-ments; other processes on the computer and random factors might have played a role. Maybe the overhead of callingnextcancels the benefit of skipping even numbers.

Exercise 1.24

Imports: The Fermat test fast-prime?, Exercise 1.22 search-for-primes

(define (prime? n) (fast-prime? n 100))

(string-contains?
 (capture-output (search-for-primes prime? 6 10))
 "7 *** ")
=> #t

$A =$ time for 3 primes greater than 1,000.

; 1009 *** .003638029098510742
; 1013 *** .003793001174926758
; 1019 *** .003606081008911133

$B =$ time for 3 primes greater than 10,000. $(0.988A < B < 1.196A)$

; 10007 *** .004311084747314453
; 10009 *** .0039730072021484375
; 10037 *** .0037479400634765625

$C =$ time for 3 primes greater than 100,000. $(0.893B < C < 1.294B)$

; 100003 *** .004847049713134766
; 100019 *** .004848003387451172
; 100043 *** .003850221633911133

$D =$ time for 3 primes greater than 1,000,000. $(0.891C < D < 1.453C)$

; 1000003 *** .005592823028564453
; 1000033 *** .004972934722900391
; 1000037 *** .0043179988861083984

Since the Fermat test has $\Theta(\log n)$ growth, time to test primes near 1,000,000 is only a bit greater than for primes near 1,000. The tests show this: for each additional order of magnitude of the primes, the time required increases by a small, constant amount. Specifically, primes that are 10 times larger take about 1 millisecond longer. These results may be dependent on the choice of 100 as the second argument to fast-prime?.

Exercise 1.25

Imports: Compound Procedures square, Exponentiation fast-expt, The Fermat test expmod

(define (alyssa-expmod base base exp m)
  (remainder (fast-expt base exp) m))

This procedure works, but it is not as efficient. The Fermat test takes much longer using alyssa-expmod—longer by three orders of magnitude. The key to the original expmod is not only successive squaring (which fast-expt does as well in Alyssa’s procedure), but also calling remainder between each squaring. Alyssa’s procedure does not, so the value becomes enormous, requiring bignums. Suppose we test primality of $n = 9$ , choosing $a = 5$ . Using the original expmod, the process evolves like so:

(define r remainder)
(define s square)
(expmod 5 9 9)
=> (r (* 5 (expmod 5 8 9)) 9)
=> (r (* 5 (r (s (expmod 5 4 9)) 9)) 9)
=> (r (* 5 (r (s (r (s (expmod 5 2 9)) 9)) 9)) 9)
=> (r (* 5 (r (s (r (s (r (s (expmod 5 1 9)) 9)) 9)) 9)) 9)
=> (r (* 5 (r (s (r (s (r (s (r (* 5 (expmod 5 0 9)) 9)) 9)) 9)) 9)) 9)
=> (r (* 5 (r (s (r (s (r (s (r (* 5 1) 9)) 9)) 9)) 9)) 9)
=> (r (* 5 (r (s (r (s (r (s (r 5 9)) 9)) 9)) 9)) 9)
=> (r (* 5 (r (s (r (s (r (s 5) 9)) 9)) 9)) 9)
=> (r (* 5 (r (s (r (s (r 25 9)) 9)) 9)) 9)
=> (r (* 5 (r (s (r (s 7) 9)) 9)) 9)
=> (r (* 5 (r (s (r 49 9)) 9)) 9)
=> (r (* 5 (r (s 4) 9)) 9)
=> (r (* 5 (r 16 9)) 9)
=> (r (* 5 7) 9)
=> (r 35 9)
=> 8

Compare this to the evolution of the process using Alyssa’s procedure:

(alyssa-expmod 5 9 9)
=> (r (fast-expt 5 9) 9)
=> (r 1953125 9)

The original expmod doesn’t need to deal with numbers anywhere near that size. This number may seem okay, but it will grow exponentially with $n$ by definition, and will quickly require arbitrary precision arithmetic, which is much slower than fixnum arithmetic.

Exercise 1.26

When the square combination is evaluated, the expmod combination is evaluated once and then its value is substituted into the square compound procedure according to the substitution model. When the squaring is written as an explicit multiplication, the #expmod combination is evaluated twice. The interpreter has no way of knowing that they will have the same value. This transforms a linear recursive process into a tree-recursive process. The time complexity of this tree-recursive process is $\Theta(\log 2^n)$ , or $\Theta(n)$ .

Exercise 1.27

Imports: Searching for divisors prime? ,The Fermat test expmod

(define (fermat-all? n) 
  (define (iter a) 
    (or (>= a n) 
	    (and (= (expmod a n n) a) 
		     (iter (+ a 1))))) 
   (iter 1))

These Carmichael numbers pass the Fermat tests for all values $a < n$ :

(fermat-all? 561) => #t
(fermat-all? 1105) => #t
(fermat-all? 1729) => #t
(fermat-all? 2465) => #t
(fermat-all? 2821) => #t
(fermat-all? 6601) => #t

According to the trial division procedure, none of them are prime:

(prime? 561) => #f
(prime? 1105) => #f
(prime? 1729) => #f
(prime? 2465) => #f
(prime? 2821) => #f
(prime? 6601) => #f

Exercise 1.28

Imports: Compound Procedures square, The Fermat test many-times

(define (square-check x m)
  (let ((sqm (remainder (square x) m)))
    (if (and (not (or (= x 1) (= x (- m 1))))
             (= sqm 1))
        0
        sqm)))
(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (square-check (expmod base (/ exp 2) m) m))
        (else (remainder (* base (expmod base (- exp 1) m))
                         m))))

(define (miller-rabin-test n)
  (define (try-it a)
    (= (expmod a (- n 1) n) 1))
  (try-it (+ 2 (random (- n 2)))))
(define (fast-prime? n times)
  (or (= times 0)
      (and (miller-rabin-test n)
           (fast-prime? n (- times 1)))))

Like the Fermat test, the Miller—Rabin test always returns true for primes but has probabilistic behavior for composite numbers:

(fast-prime? 13 many-times) => #t 
(fast-prime? 10 many-times) =?> [#f #t] ; correct answer is #f

Unlike the Fermat test, it is not fooled by Carmichael numbers:

(fast-prime? 561 many-times) =?> [#f #t] ; correct answer is #f