SICP Study

1.2 Procedures and the Processes They Generate

To become experts, we must learn to visualize the processes generated by various types of procedures. Only after we have developed such a skill can we learn to reliably construct programs that exhibit the desired behavior. (Section 1.2)

1.2.1 Linear Recursion and Iteration

(factorial 4)
(* 4 (factorial 3))
(* 4 (* 3 (factorial 2)))
(* 4 (* 3 (* 2 (factorial 1))))
(* 4 (* 3 (* 2 1)))
(* 4 (* 3 2))
(* 4 6)
24
(factorial 4)
(fact-iter 1 1 4)
(fact-iter 1 2 4)
(fact-iter 2 3 4)
(fact-iter 6 4 4)
(fact-iter 24 5 4)
24

1.2.2 Tree Recursion

In general, the number of steps required by a tree-recursive process will be proportional to the number of nodes in the tree, while the space required will be proportional to the maximum depth of the tree. (Section 1.2.2)

Example: Counting change

Let f(A,N)f(A,N) represent the number of ways of changing the amount AA using NN kinds of coins. If the first kind of coin has denomination N,N\htmlClass{math-punctuation}{\text{,}} then f(A,N)=f(A,N1)+f(AD,N).f(A,N) = f(A,N-1) + f(A-D,N)\htmlClass{math-punctuation}{\text{.}} In words, there are two situations: where you do not use any of the first kind of coin, and when you do. The value of f(A,N1)f(A,N-1) assumes we don’t use the first kind at all; the value of f(AD,N)f(A-D,N) assumes we use one or more of the first kind.

That rule and a few degenerate cases are sufficient to describe an algorithm for counting the number of ways of changing amounts of money. We can define it with the following piecewise function:

f(A,N)={1,if A=0,0,if A<0 or N=0,f(A,N1)+f(AD,N),if A>0 and N>0.f(A,N) = \begin{cases} 1, & \text{if $A = 0$,} \\ 0, & \text{if $A < 0$ or $N = 0$,} \\ f(A,N-1) + f(A-D,N), & \text{if $A > 0$ and $N > 0$.} \end{cases}

Like Fibonacci, the easy tree-recursive implementation involves a lot of redundancy. Unlike it, there is no obvious iterative solution (it is possible, just harder). One way to improve the performance of the tree-recursive process is to use memoization.

1.2.3 Orders of Growth

1.2.4 Exponentiation

One way to calculate bb to the nthn\htmlClass{math-punctuation}{\text{th}} power is via the following recursive definition:

b0=1,bn=bbn1.b^0 = 1, \qquad b^n = b * b^{n-1}.

A faster method is to use successive squaring:

bn={(bn/2)2,if n is even,bbn1,if n is odd.b^n = \begin{cases} \left(b^{n/2}\right)^2, & \text{if $n$ is even,} \\ b * b^{n-1}, & \text{if $n$ is odd.} \end{cases}

1.2.5 Greatest Common Divisors

(gcd 206 40)
(gcd 40 6)
(gcd 6 4)
(gcd 4 2)
(gcd 2 0)
2

1.2.6 Example: Testing for Primality

Searching for divisors

The Fermat test

The Fermat test is a Θ(log(n))Θ(log(n)) primality test based on Fermat’s Little Theorem:

If nn is a prime number and aa is any positive integer less than n,n\htmlClass{math-punctuation}{\text{,}} then aa raised to the nthn\htmlClass{math-punctuation}{\text{th}} power is congruent to aa modulo n.n\htmlClass{math-punctuation}{\text{.}} (Section 1.2.6)

The test works like this:

  1. Given a number n,n\htmlClass{math-punctuation}{\text{,}} pick a random number a<na < n and calculate anmodn.a^n\bmod n\htmlClass{math-punctuation}{\text{.}}
  2. Fail: If the result is not equal to a,a\htmlClass{math-punctuation}{\text{,}} then nn is not prime.
  3. Pass: If the result is equal to a,a\htmlClass{math-punctuation}{\text{,}} then nn is likely prime.
  4. Repeat. The more times the number passes the test, the more confident we are that nn is prime. If there is a single failure, nn is certainly not prime.

Probabilistic methods

Highlights

Numbers that fool the Fermat test are called Carmichael numbers, and little is known about them other than that they are extremely rare. … In testing primality of very large numbers chosen at random, the chance of stumbling upon a value that fools the Fermat test is less than the chance that cosmic radiation will cause the computer to make an error in carrying out a “correct” algorithm. Considering an algorithm to be inadequate for the first reason but not for the second illustrates the difference between mathematics and engineering. (Footnote 1.47)