Fun With the Fibonacci Series -- a Pascal Exercise

The Fibonacci series 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 .. is defined by the following iteration rule: The first two numbers are equal to one, and each remaining number is the sum of the two preceding numbers.

Thus, we add the first two numbers to get the third: 1+1 = 2.  Then we add the second and third numbers to get the fourth: 1+2 = 3.  Next, third plus fourth equals the fifth: 2+3 = 5.  Continuing, 3+5=8, 5+8=13, 8+13=21, etc.

Here is a small Pascal program that generates the first 20 values of the Fibonacci series:

```program Fib1;  {Fibonacci series}

const
Lim = 20;

var
F: array[1..Lim] of integer;
I: integer;

begin
F[1]:= 1;
F[2]:= 1;
write('1 1');
for I:= 3 to Lim do begin
F[I]:= F[I-1] + F[I-2];
write(' ', F[I]);
end;
end.```

The program output is: 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

Before the 'for' loop starts, we write the first two values, because the loop only does the remaining values.

We defined the constant Lim so that we can change its value by editing only one spot in the program.  If we had written

`    F: array[1..20] of integer;`

and

`    for I:= 3 to 20 do begin`

then we would need to edit both these lines to change the limit value of 20.

To better see how the program works, set up the variables F and I in a watch window and single-step through the program, watching how the values of the variables change.

Try increasing the value of Lim.  What happens?  If we make Lim greater than 23, we get an arithmetic overflow error.  In Turbo Pascal and Borland Pascal, integers are two bytes, or 16 bits long, with a maximum value of 32767.

But a longint is four bytes, or 32 bits long, with a maximum value of 2147483647.  Suppose we make F an array of longints rather than integers.  Longints are twice the size of integers, so perhaps we can double the value of Lim.   Try these changes:

```const
Lim = 46;

var
F: array[1..Lim] of longint;```

Can Lim be increased further?

The 'comp' type is basically a 64-bit integer, although it is considered one of the 'real' types, because it is processed by the same hardware in the computer.  So we can try these changes:

```const
Lim = 92;

var
F: array[1..Lim] of comp;```

But we should also change the write statement so that the values will be formatted like integers:

`    write(' ', F[I]:1:0);`

Now we can generate some really BIG numbers!  The last value generated is 7540113804746346430.

One of the interesting things about the Fibonacci series is that the ratio of two successive numbers, that is, F[I] / F[I-1], becomes closer and closer to the Golden Ratio 1.61803398874989 as the numbers get larger.

The Golden Ratio, which fascinated the ancient Greek architects, has interesting properties.  For example, if a rectangle whose length is the Golden Ratio times its width is cut in half parallel to a short side, each half has the same proportions as the original rectangle.

The Golden Ratio can be calculated by adding one to the square root of five, then dividing by two.  In Pascal, this is:

`    (Sqrt(5.0)+1.0)/2.0`

We want the calculations to use real values (with decimal fractions), so we write the constants as "5.0", "1.0", and "2.0" rather than as "5", "1", and "2".

We can demonstrate the relationship of the Golden Ratio to the Fibonacci series by the following modification of the program:

```program Fib2;  {Fibonacci series}

const
Lim = 45;

var
F: array[1..Lim] of comp;
I: integer;
R: extended;

begin
F[1]:= 1;
F[2]:= 1;
for I:= 3 to Lim do begin
F[I]:= F[I-1] + F[I-2];
R:= F[I] / F[I-1];
writeln(R:19:17, ' ', F[I]:1:0);
end;
writeln((Sqrt(5.0)+1.0)/2.0:19:17);
end.```

Just as we have different sizes of integers (shortint, integer, and longint) to use according as speed or memory space may be more important, we also have different sizes of real numbers.  Turbo Pascal and Borland Pascal provide the real types:

```    single   (4 bytes)
real     (6 bytes)
double   (8 bytes)
extended (10 bytes)```

We have chosen the extended precision type to compute the greatest number of digits that the computer can handle.

The ':19:17' allows 19 spaces for each number, with 17 digits after the decimal point.

Can you discover other properties of the Fibonacci series?

Can you extend the Fibonacci series in the other direction?  That is, what numbers precede the 1, 1?  For example, what number plus 1 equals 1?  (0)  What number plus 0 equals 1?  (1)  What number plus 1 equals 0?  (-1)  What number plus -1 equals 1?  (2)  See the partial series below:

`.. 2 -1 1 0 1 1 2 3 5 8 ..`

If you didn't understand the above paragraph the first time that you read it, examine the partial series carefully and read the paragraph again.

There is another way to program an iteration rule without using an array.  This could be useful for a very long iteration where the array might be too big for the available memory.  Instead of working with three successive elements of an array such as F[I-2], F[I-1], and F[I], we use three separate variables such as A, B, and C.

We start by initializing the first two values:

`    A:= 1;  B:= 1;`

Then, in a loop, we calculate the next value:

`    C:= A + C;`

At the end of the loop, to prepare for the next repetition of the loop, we shift the values, moving the value to B to A, and the value of C to B.  The data flow pattern is:

`    A <-- B <-- C`

The Pascal statements for this are:

`    A:= B;  B:= C;`

The order of these statements is important. If we write

`    B:= C;  A:= B;`

the value of C would move to B, then to A, and the value of B would be lost.

Using this method, we don't need to count the iterations using a variable such as I.  (But we could if we wanted.)  We need a method for stopping the loop, however.  One way to do this is to stop when the last value computed exceeds some chosen value.  For example, if the chosen value were the maximum value divided by the Golden Ratio, the loop would stop just before making an arithmetic overflow error.

Here is another version of the program that uses the shifting method in a 'repeat .. until' loop, and that produces exactly the same output as before:

```program Fib3;  {Fibonacci series}

var
A, B, C: comp;
R: extended;

begin
A:= 1;
B:= 1;
repeat
C:= A + B;
R:= C / B;
writeln(R:19:17, ' ', C:1:0);
A:= B;  B:= C;  {shift}
until C > 1000000000.0;
writeln((Sqrt(5.0)+1.0)/2.0:19:17);