Structure and Interpretation of Computer Programs (12 page)

²⁹
In a real program we would probably use the
block structure introduced in the last section to hide the definition
of
fact-iter
:

(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product)
              (+ counter 1))))
  (iter 1 1))

We avoided doing this here so as to minimize the number of things to
think about at once.

³⁰
When we discuss the implementation of
procedures on register machines in chapter 5, we will see that any
iterative process can be realized “in hardware” as a machine that
has a fixed set of registers and no auxiliary memory. In contrast,
realizing a recursive process requires a machine that uses an
auxiliary data structure known as a
stack
.

³¹
Tail recursion has long been
known as a compiler optimization trick. A coherent semantic basis for
tail recursion was provided by Carl Hewitt (1977), who explained it in
terms of the “message-passing” model of computation that we shall
discuss in chapter 3. Inspired by this, Gerald Jay Sussman and Guy
Lewis Steele Jr. (see Steele 1975) constructed a tail-recursive
interpreter for Scheme. Steele later showed how tail recursion is a
consequence of the natural way to compile procedure calls (Steele
1977). The IEEE standard for Scheme requires that Scheme implementations
be tail-recursive.

³²
An example of this was hinted
at in section 
1.1.3
:
The interpreter itself evaluates expressions
using a tree-recursive process.

³³
For example, work through in detail how the
reduction rule applies to the problem of making change for 10 cents
using pennies and nickels.

³⁴
One
approach to coping with redundant computations is to arrange matters
so that we automatically construct a table of values as they
are computed. Each time we are asked to apply the procedure to some
argument, we first look to see if the value is already stored in the
table, in which case we avoid performing the redundant computation.
This strategy, known as
tabulation
or
memoization
, can be
implemented in a straightforward way. Tabulation can sometimes be
used to transform processes that require an exponential number of
steps (such as
count-change
) into processes whose space and time
requirements grow linearly with the input. See
exercise 
3.27
.

³⁵
The elements of Pascal's triangle are called the
binomial
coefficients
, because the
n
th row consists of
the coefficients of the terms in the
expansion of (
x
+
y
)
ⁿ
. This pattern for computing the coefficients
appeared in Blaise Pascal's 1653 seminal work on probability theory,
Traité du triangle arithmétique
. According to
Knuth (1973), the same pattern appears in the
Szu-yuen
Yü-chien
(“The Precious Mirror of the Four Elements”), published
by the Chinese mathematician Chu Shih-chieh in 1303, in the
works of the twelfth-century Persian poet and mathematician Omar
Khayyam, and in the works of the twelfth-century Hindu mathematician
Bháscara Áchárya.

³⁶
These statements mask a
great deal of oversimplification. For instance, if we count process
steps as “machine operations” we are making the assumption that the
number of machine operations needed to perform, say, a multiplication
is independent of the size of the numbers to be multiplied, which is
false if the numbers are sufficiently large. Similar remarks hold for
the estimates of space. Like the design and description of a process,
the analysis of a process can be carried out at various levels of
abstraction.

³⁷
More precisely, the number of multiplications
required is equal to 1 less than the log base 2 of
n
plus the number
of ones in the binary representation of
n
. This total is always
less than twice the log base 2 of
n
. The arbitrary constants
k
₁
and
k
₂
in
the definition of order notation imply that, for a logarithmic
process, the base to which logarithms are taken does not matter, so
all such processes are described as θ(
log
n
).

³⁸
You may wonder
why anyone would care about raising numbers to the 1000th power. See
section 
1.2.6
.

³⁹
This iterative
algorithm is ancient. It appears in the
Chandah-sutra
by
Áchárya Pingala, written before 200
B
.
C
. See Knuth 1981, section
4.6.3, for a full discussion and analysis of this and other methods of
exponentiation.

⁴⁰
This
algorithm, which is sometimes known as the “Russian peasant method”
of multiplication, is ancient. Examples of its use are found in the
Rhind Papyrus, one of the two oldest mathematical documents in
existence, written about 1700
B
.
C
. (and copied from an even
older document) by an Egyptian scribe named A'h-mose.

⁴¹
This exercise was
suggested to us by Joe Stoy, based on an example in Kaldewaij 1990.

⁴²
Euclid's Algorithm is so
called because it appears in Euclid's
Elements
(Book 7, ca. 300
B
.
C
.). According to Knuth (1973), it can be considered the
oldest known nontrivial algorithm. The ancient Egyptian method of
multiplication (exercise 
1.18
) is surely older,
but, as Knuth explains, Euclid's algorithm is the oldest known to have
been presented as a general algorithm, rather than as a set of
illustrative examples.

⁴³
This theorem was proved in 1845 by Gabriel Lamé, a
French mathematician and engineer known chiefly for his contributions
to mathematical physics. To prove the theorem, we consider pairs
(
a
_k
,
b
_k
), where
a
_k
>
b
_k
, for which Euclid's Algorithm
terminates in
k
steps. The proof is based on the claim that, if
(
a
_k
+1
,
b
_k
+1
) ⟶ (
a
_k
,
b
_k
)
⟶ (
a
_k
-1
,
b
_k
-1
) are three successive pairs in the
reduction process, then we must have
b
_k
+1
>
b
_k
+
b
_k
-1
.
To verify the claim, consider that a reduction step is defined by
applying the transformation
a
_k
-1
=
b
_k
,
b
_k
-1
=
remainder of
a
_k
divided by
b
_k
.
The second equation means that
a
_k
=
q
b
_k
+
b
_k
-1
for some
positive integer
q
. And since
q
must be at least 1 we have
a
_k
=
q
b
_k
+
b
_k
-1
>
b
_k
+
b
_k
-1
. But in the previous
reduction step we have
b
_k
+1
=
a
_k
. Therefore,
b
_k
+1
=
a
_k
>
b
_k
+
b
_k
-1
. This verifies the claim. Now we can
prove the theorem by induction on
k
, the number of steps that the
algorithm requires to terminate. The result is true for
k
= 1, since
this merely requires that
b
be at least as large as
F
i
b
(1) = 1. Now, assume that the result is true for all integers less
than or equal to
k
and establish the result for
k
+ 1. Let
(
a
_k
+1
,
b
_k
+1
) ⟶ (
a
_k
,
b
_k
)
⟶ (
a
_k
-1
,
b
_k
-1
) be successive pairs in the
reduction process. By our induction hypotheses, we have
b
_k
-1
>
F
i
b
(
k
- 1) and
b
_k
>
F
i
b
(
k
). Thus, applying the claim we just
proved together with the definition of the Fibonacci numbers gives
b
_k
+1
>
b
_k
+
b
_k
-1
>
F
i
b
(
k
) +
F
i
b
(
k
- 1) =
F
i
b
(
k
+ 1), which
completes the proof of Lamé's Theorem.

⁴⁴
If
d
is a divisor of
n
, then so is
n
/
d
.
But
d
and
n
/
d
cannot both be greater than √
n
.

⁴⁵
Pierre de Fermat (1601-1665) is considered to be the founder of
modern number theory. He obtained many important number-theoretic
results, but he usually announced just the results, without providing
his proofs.
Fermat's Little Theorem was stated in a letter he wrote in
1640. The first published proof was given by
Euler in 1736 (and an
earlier, identical proof was discovered in the unpublished manuscripts
of Leibniz). The most famous of Fermat's results – known as Fermat's
Last Theorem – was jotted down in 1637 in his copy of the book
Arithmetic
(by the third-century Greek mathematician
Diophantus) with the
remark “I have discovered a truly remarkable proof, but this margin is
too small to contain it.” Finding a proof of Fermat's Last Theorem
became one of the most famous challenges in number theory. A complete
solution was finally given in 1995 by Andrew Wiles of Princeton University.

⁴⁶
The reduction steps in the cases where the exponent
e
is greater than 1 are based on the fact that, for any integers
x
,
y
, and
m
, we can find the remainder of
x
times
y
modulo
m
by computing separately the remainders of
x
modulo
m
and
y
modulo
m
, multiplying these, and then taking the remainder of the
result modulo
m
. For instance, in the case where
e
is even, we
compute the remainder of
b
^e
/2
modulo
m
, square this, and take
the remainder modulo
m
. This technique is useful because it means
we can perform our computation without ever having to deal with
numbers much larger than
m
. (Compare
exercise 
1.25
.)

⁴⁷
Numbers that fool the
Fermat test are called
Carmichael numbers
, and little is known
about them other than that they are extremely rare. There are 255
Carmichael numbers below 100,000,000. The smallest few are 561, 1105,
1729, 2465, 2821, and 6601. 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.

⁴⁸
One of the most striking applications of
probabilistic prime testing has been to the field of cryptography.
Although it is now computationally infeasible to factor an arbitrary
200-digit number, the primality of such a number can be checked in a
few seconds with the Fermat test. This fact forms the basis of a
technique for constructing “unbreakable codes” suggested by
Rivest,
Shamir, and
Adleman (1977). The resulting
RSA algorithm
has
become a widely used technique for enhancing the security of
electronic communications. Because of this and related developments,
the study of
prime numbers, once considered the epitome of a topic in
“pure” mathematics to be studied only for its own sake, now turns
out to have important practical applications to cryptography,
electronic funds transfer, and information retrieval.