Generation of the Fibonacci sequence

This blog explains about fibonacci sequence,

Generate and print the first~ terms of the Fibonacci sequence where n~ 1. The first few terms are

                                    0, 1, 2, 3, 5, 8, 13, ...

Each term beyond the first two is derived from the sum of its two nearest predecessors.

Algorithm development

From the definition: new term = preceding term- before preceding term. The last sentence of the problem statement suggests we may be able to use the definition to generate consecutive terms (apart from the first two) iteratively.

            Define:

                                    a as the term before the preceding term

                                    b as the preceding term

                                    c new term

            Then to start with:

                                    a:= 0    first fibonacci number

                                    b := 1  second Fibonacci number

                                    c := a+b  third Fibonacci number (from definition)

            When the new term c has been generated we have the third Fibonacci. To generate the fourth, or next Fibonacci number, we need to apply the same definition again. Before we can make this next computation we  need to make some adjustments. The fourth Fibonacci number is derived

From the sum of the second and third Fibonacci numbers. With regard to the definition the second Fibonacci number has the role of the term before the preceding term and the third Fibonacci number has the role of "the preceding term". Therefore ,before making the next (i.e. the fourth) computation we must ensure that:

            a) new term (i.e. the third) assumes the role of the preceding term,

            (b) and what is currently the preceding term must assume the role of the term before the   

                 preceding term.

            That is,

                        a:= 0                [1]        term before preceding term

                        b := 1              [2]        preceding term

                        c := a+b          [3]        new term

                        a:= b               [4]        term before preceding term becomes preceding term

                        b := c                [5]         preceding term becomes new term

After making step [5] we are in a position where we can use the definition to generate the next Fibonacci number. A way to do this is to loop back to step [3]. Further investigation of steps [3]->[5] indicates they can be placed in a loop to iteratively generate Fibonacci numbers (for n>2). The essential mechanism we could use is:

                                                a:= 0;

                                                b := 1;

                                                i:= 2;

                                                while i<n do

                                                begin

                                                            i:=i+l;

                                                            c := a+b;

                                                            a:= b;

                                                            b = c;

                                                end

As each new term c is Computed, the term before the preceding term, a, loses its relevance to the Calculation of the next Fibonacci number. To restore its relevance assignment is done. At all times only two numbers are relevant to the generation of the next Fibonacci number. In our computation, a third variable, c is introduced. Keep the two variables a and b always relevant. Because the first Fibonacci number becomes irrelevant as soon as the third Fibonacci is computed, start with:

                                                a:= 0;  [1]

                                                b := 1; [2]

                                                a := a+b [3]

Iterate on step [3] to generate successive Fibonacci numbers we run into trouble because we are not changing b. However, after step [3] we know the next (i.e. fourth) Fibonacci number can be generated using,

                                                next:=a+b;

Doing step [4], the old value of b, as defined by step [2], loses its relevance. To keep b  relevant at step [4] we can make the assignment:

                                                b := a+b

The first four steps then become

                                                a:= 0;              [1]

                                                b := 1;             [2]

                                                a := a+p;         [3]       

                                                b := a+b          [4]

After step [4]  find that a and b as defined are correct for generating the fifth Fibonacci number. At this point the old a value becomes irrelevant. Working through several more steps confirms that we can safely iterate on steps [3] and [4] to generate the required sequence. Because the algorithm generates Fibonacci numbers in pairs care must be taken to write out exactly n numbers. The easiest way to do this is to keep the output one step behind the generation phase. The complete algorithm description can now be given.

Algorithm description

1. Prompt and read n, the number of Fibonacci numbers to be generated.

2. Assign first two Fibonacci numbers a and b.

3. Initialize count of number generated.

4. While less than n Fibonacci numbers have been generated do

(a) write out next two Fibonacci numbers;

(b) generate next Fibonacci number keeping a relevant;

(c) generate next Fibonacci number from most recent pair keeping b relevant for next computation;

(d) update count of number of Fibonacci numbers generated, i.

5. If n even then write out last two Fibonacci numbers else write out second last Fibonacci number.