TAOCP 1.2.8 Exercise 3

Exercise 2 shows that F_n = \phi^n/\sqrt{5} \text{ rounded to the nearest integer,} by Eq.

taocpmathematicsalgorithmsvolume-1medium

Section 1.2.8: Fibonacci Numbers

Exercise 3. [25] Write a computer program that calculates and prints $F_1$ through $F_{1000}$ in decimal notation. (The previous exercise determines the size of numbers that must be handled.)

Verified: no
Solve time: -

Solution

Exercise 2 shows that

$$ F_n = \phi^n/\sqrt{5} \text{ rounded to the nearest integer,} $$

by Eq. (15), and therefore $F_{1000}$ has approximately

$$ 1000\log_{10}\phi-\log_{10}\sqrt{5}+1 $$

decimal digits. Since

$$ \log_{10}\phi \approx 0.208987\ldots, \qquad \log_{10}\sqrt{5}\approx 0.349485\ldots, $$

we obtain

$$ 1000\log_{10}\phi-\log_{10}\sqrt{5}+1 \approx 209.638\ldots . $$

Hence $F_{1000}$ has $209$ decimal digits. Any program for this exercise must therefore manipulate integers substantially larger than ordinary machine word size.

The Fibonacci recurrence

$$ F_n = F_{n-1}+F_{n-2} $$

suggests an iterative computation. If arbitrary-precision decimal integers are represented as arrays of digits, least significant digit first, the addition required at each stage may be carried out exactly as in ordinary decimal arithmetic.

Let $A$ represent $F_{n-1}$ and $B$ represent $F_n$. Initially,

$$ A=F_0=0,\qquad B=F_1=1. $$

At each stage the program prints $B$, computes

$$ C\leftarrow A+B, $$

then replaces

$$ A\leftarrow B,\qquad B\leftarrow C. $$

After the update,

$$ A=F_n,\qquad B=F_{n+1}, $$

so the invariant is preserved.

A suitable program is therefore:

A ← 0
B ← 1
for n ← 1 step 1 until 1000 do
begin
    print B
    C ← A + B
    A ← B
    B ← C
end

The only nontrivial operation is the addition of arbitrarily long decimal integers. Since $F_{1000}$ has $209$ digits, storage for at least $209$ decimal digits per number suffices.

Thus the problem reduces to repeated multiple-precision addition, and the program prints exactly

$$ F_1,F_2,\ldots,F_{1000} $$

in decimal notation.

$$ \boxed{\text{Use iterative Fibonacci generation with multiple-precision decimal addition, storing at least 209 digits.}} $$