# 1.2 Procedures and the Processes They Generate⁠

# 1.2.1 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\htmlClass{math-punctuation}{\text{,}}$ since (A 0 n) => (* 2 n).

(g n) computes $2^n\htmlClass{math-punctuation}{\text{,}}$ since (A 1 n) => (A 0 (A 1 (- n 1))) => (f (g (- n 1))).

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

(k n) computes $5n^2\htmlClass{math-punctuation}{\text{,}}$ as stated in the exercise.

# 1.2.2 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

# 1.2.2.1 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 $\varphi$ and $\psi$ are the solutions to golden ratio equation $x+1=x^2\htmlClass{math-punctuation}{\text{:}}$

$$\varphi=\frac{1+\sqrt5}{2},\qquad\psi=\frac{1-\sqrt5}{2}.$$

The Fibonacci sequence is defined recursively by

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

Lemma. $\Fib(n)$ is equal to $f(n)=\dfrac{\varphi^n-\psi^n}{\sqrt5}.$

Proof. First, we will demonstrate three base cases. When $n=0\htmlClass{math-punctuation}{\text{,}}$

$$f(0)=\frac{\varphi^0-\psi^0}{\sqrt5} = \frac{1-1}{\sqrt5} = 0.$$

When $n=1\htmlClass{math-punctuation}{\text{,}}$

$$f(1)=\frac{\varphi^1-\psi^1}{\sqrt5} = \frac{\frac{1+\sqrt5}{2}-\frac{1-\sqrt5}{2}}{\sqrt5} = \frac{\frac{2\sqrt5}{2}}{\sqrt5} = 1.$$

When $n=2\htmlClass{math-punctuation}{\text{,}}$

$$\begin{aligned} f(2) &= \frac{\varphi^2-\psi^2}{\sqrt5} \\ &= \frac{\left(\frac{1+\sqrt5}{2}\right)^2 - \left(\frac{1-\sqrt5}{2}\right)^2}{\sqrt5} \\ &= \frac{\frac{(1+\sqrt5)^2-(1-\sqrt5)^2}{4}}{\sqrt5} \\ &= \frac{\left(\left(1+\sqrt5\right)-\left(1-\sqrt5\right)\right) \left(\left(1+\sqrt5\right)+\left(1-\sqrt5\right)\right)}{4\sqrt5} \\ &= \frac{\left(2\sqrt5\right)(2)}{4\sqrt5} \\ &= 1. \end{aligned}$$

Now comes the inductive step:

$$\begin{aligned} f(n-1)+f(n-2) &= \frac{\varphi^{n-1}-\psi^{n-1}}{\sqrt5} + \frac{\varphi^{n-2}-\psi^{n-2}}{\sqrt{5}} \\ &= \frac{\left(\varphi^{n-1}+\varphi^{n-2}\right) - \left(\psi^{n-1}+\psi^{n-2}\right)}{\sqrt5} \\ &= \frac{\varphi^n\left(\varphi^{-1}+\varphi^{-2}\right) - \psi^n\left(\psi^{-1}+\psi^{-2}\right)}{\sqrt5} \\ &= \frac{\varphi^n\varphi^{-1}\left(1+\varphi^{-1}\right) - \psi^n\psi^{-1}\left(1+\psi^{-1}\right)}{\sqrt5} \\ &= \frac{\varphi^n\varphi^{-1}\left(\varphi\right) - \psi^n\psi^{-1}\left(\psi\right)}{\sqrt5} \\ &= \frac{\varphi^n-\psi^n}{\sqrt5} \\ &= f(n). \end{aligned}$$

By induction, $f(n)=\Fib(n)$ for all $n\htmlClass{math-punctuation}{\text{.}}$ $\blacksquare$

Theorem. $\Fib(n)$ is the closest integer to $\dfrac{\varphi^n}{\sqrt5}\htmlClass{math-punctuation}{\text{,}}$ where $\varphi=\dfrac{1+\sqrt5}{2}\htmlClass{math-punctuation}{\text{.}}$

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

$$\begin{aligned} \abs{\Fib(n)-\frac{\varphi^n}{\sqrt5}} &< \frac12 \\ \abs{\frac{\varphi^n-\psi^n}{\sqrt5} - \frac{\varphi^n}{\sqrt5}} &< \frac12\\ \abs{-\frac{\psi^n}{\sqrt5}} &< \frac12 \\ \frac{\abs{-\psi^n}}{\sqrt5} &< \frac12 \\ \abs{\psi}^n &< \frac{\sqrt5}{2}. \end{aligned}$$

Since $\abs{\psi}<0.619<1\htmlClass{math-punctuation}{\text{,}}$ we have $\abs{\psi}^n<1<\dfrac{\sqrt5}{2}$ for all $n\htmlClass{math-punctuation}{\text{.}}$ $\blacksquare$

# 1.2.3 Orders of Growth⁠

# Exercise 1.14⁠

(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: $Θ(n^5)$ because there are 5 types of coins.
• Space: $Θ(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)))))

1. The procedure p is 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

2. During the process, p is evaluated $k$ times such that $θ/3^k<0.1\htmlClass{math-punctuation}{\text{.}}$ Solving for $k$ gives $k = \log10θ/\log3\htmlClass{math-punctuation}{\text{,}}$ thus the number of steps for sine grows as $Θ(\log n)\htmlClass{math-punctuation}{\text{.}}$ The interpreter must maintain the stack for that number of calls to p, so the space complexity is also $Θ(\log n)\htmlClass{math-punctuation}{\text{.}}$

# 1.2.4 Exponentiation⁠

Recursive, naive: $Θ(n)$ time, $Θ(n)$ space.

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

(expt 2 5) => 32

Iterative, naive: $Θ(n)$ time, $Θ(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, successive squaring: $Θ(\log n)$ time, $Θ(\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⁠

Iterative, successive squaring: $Θ(\log n)$ time, $Θ(1)$ 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: $Θ(n)$ time, $Θ(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, successive doubling: $Θ(\log n)$ time, $Θ(\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⁠

Iterative, successive doubling: $Θ(\log n)$ time, $Θ(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))

(fast-* 5 4) => 20

# Exercise 1.19⁠

Let $T_{pq}(a, b) = (bq + aq + ap, bp + aq)\htmlClass{math-punctuation}{\text{.}}$ Applying $T_{pq}$ twice gives

$$\begin{aligned} &\phantom{=} T_{pq}(T_{pq}(a, b)) \\ &= T_{pq}(bq + aq + ap, bp + aq) \\ &= ((bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p, \\ &\phantom{= (} (bp + aq)p + (bq + aq + ap)q) \\ &= (bpq + aq^2 + bq(q + p) + aq(q + p) + ap(q + p), \\ &\phantom{= (} bp^2 + aqp + bq^2 + aq^2 + apq) \\ &= (bpq + aq^2 + bq^2 + bpq + aq^2 + apq + apq + ap^2, \\ &\phantom{= (} bp^2 + apq + bq^2 + aq^2 + apq) \\ &= (b(q^2 + 2pq) + a(q^2 + 2pq) + a(p^2 + q^2), \\ &\phantom{= (} 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\htmlClass{math-punctuation}{\text{.}}$

Using this, we can implement fib with $Θ(\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

# 1.2.5 Greatest Common Divisors⁠

Euclid’s Algorithm: $Θ(\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.

(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)))

# 1.2.6 Example: Testing for Primality⁠

# 1.2.6.1 Searching for divisors

(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: $Θ(\sqrt n)$ time.

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

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

# 1.2.6.2 The Fermat test

(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: $Θ(\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⁠

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

# Exercise 1.22⁠

(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,000. $(3.3B < C < 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 $Θ(\sqrt n)$ prediction. The growth between powers of ten gets closer to $\sqrt{10}\approx3.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 required for the computation.

# Exercise 1.23⁠

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 measurements; other processes on the computer and random factors might have played a role. Maybe the overhead of calling next cancels the benefit of skipping even numbers.

# Exercise 1.24⁠

(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 $Θ(\log n)$ growth, I expected the time to test primes near 1,000,000 to be only a bit greater than for primes near 1,000. The data bears this out: 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? (the exercise did not specify what value to use).

# Exercise 1.25⁠

(define (alyssa-expmod 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 the primality of $n=9\htmlClass{math-punctuation}{\text{,}}$ choosing $a=5\htmlClass{math-punctuation}{\text{.}}$ 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 the 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 $Θ(\log 2^n)\htmlClass{math-punctuation}{\text{,}}$ or $Θ(n)\htmlClass{math-punctuation}{\text{.}}$

# Exercise 1.27⁠

(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\htmlClass{math-punctuation}{\text{:}}$

(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⁠

(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 in § 1.2.6, the Miller–Rabin test always returns true for primes but has probabilistic behavior for composites 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