Structure and Interpretation of Computer Programs by Harold Abelson and Gerald Jay Sussman with Julie Sussman
Ads: Link
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.
36 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.
37 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
1 and
k
2 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
).
38 You may wonder
why anyone would care about raising numbers to the 1000th power. See
section 1.2.6 .
39 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.
40 Thisalgorithm, which is sometimes known as the “Russian peasant method”
of multiplication, is ancient. Examples of its use are found in theRhind Papyrus, one of the two oldest mathematical documents in
existence, written about 1700
B
.
C
. (and copied from an evenolder document) by an Egyptian scribe named A'h-mose.
41 This exercise wassuggested to us by Joe Stoy, based on an example in Kaldewaij 1990.
42 Euclid's Algorithm is socalled because it appears in Euclid's
Elements
(Book 7, ca. 300
B
.
C
.). According to Knuth (1973), it can be considered theoldest 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.
43 This theorem was proved in 1845 by Gabriel Lamé, aFrench 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.
44 If
d
is a divisor
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.
36 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.
37 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
1 and
k
2 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
).
38 You may wonder
why anyone would care about raising numbers to the 1000th power. See
section 1.2.6 .
39 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.
40 Thisalgorithm, which is sometimes known as the “Russian peasant method”
of multiplication, is ancient. Examples of its use are found in theRhind Papyrus, one of the two oldest mathematical documents in
existence, written about 1700
B
.
C
. (and copied from an evenolder document) by an Egyptian scribe named A'h-mose.
41 This exercise wassuggested to us by Joe Stoy, based on an example in Kaldewaij 1990.
42 Euclid's Algorithm is socalled because it appears in Euclid's
Elements
(Book 7, ca. 300
B
.
C
.). According to Knuth (1973), it can be considered theoldest 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.
43 This theorem was proved in 1845 by Gabriel Lamé, aFrench 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.
44 If
d
is a divisor
Similar Books
