Loop Example: Fibonacci Sequences

Home, Up: Loop and Script Examples

In this example:

$ and $$, Result Buffer, Accumulation Mode, WHISK, ITEM, DONE.

As always, the question mark at the beginning of a line is Hypatia's input prompt, yu do not type it.

The famous Fibonacci sequence is a sequence of numbers that starts with 0 and 1, with each following element being the sum of its two predecessors:

0 1 1 2 3 5 8 13 21 34 ...

With the help of $ (last result) and $$ (last but one result) this is easy to compute -- for instance, with this script, let's call it fibo:

Now we can calculate the first 20 Fibonacci numbers:

(Actually with 20 passes we have arrived at the 21st Fibonacci number, but that's mostly a matter of definition and doesn't need to concern us here. If you correctly want the nth Fibonacci number, call this script with n-1 loop passes.)

With longer sequences our script should use buffer mode to make it faster:

If you are only interested in the nth number but do not need the whole sequence, we don't need a script, we can just say

(Again, with 20 loop passes we arrive at the 21st Fibonacci number.)

Fascinating as Fibonacci sequences are, there isn't much point in calculating them, because it's already been done. (By the way, Hypatia exactly calculates them up to the 87th Fibonacci number, from the 88th on they have more than 18 digits and will be rounded, but may still be useful as approximations.)

More interesting to us here are generalized Fibonacci sequences. There are (at least) four ways in which generalization is possible, which can also be combined:

- by using different start values than 0 and 1,

- by using different arithmetic operations than addition, including operations that have non-integer results,

- by introducing an element of randomness in various ways,

- and finally by making new elements of the sequence depend on more than the two preceding ones.

Our script can be easily modified to accomodate the first two generalisations, and, depending on what exactly we want to do, also the third one.

If we want to calculate the next element from more than the two previous ones, it becomes more difficult, though. We could use variables, but first let's look at DONE instead.

For the original Fibonacci sequence as discussed above, instead of using $ and $$ for the two previous results we could use the two last values in the buffer -- this is slower and has no immediate advantage, but we can then use this method to base our calculation on more than two elements.

and, this would immediately end with an error. After the first loop pass the buffer would have the numbers 0 1 1 -- then, in the second pass, the calulation to perform would be 0 1 1 + -- 1 and 1 is 2, the line would now be 0 2 with no further operation to perform, and we'd get "Error: argument count mismatch, remaining on stack: 1".

To avoid this, we need the DONE pseudo operator (see page "Pseudo Operators" in chapter "Operators and Constants") -- with it we can tell Hypatia not to bother about any remaining numbers to its left.

Here is the correct script:

And now we could easily create a sequence where each element is the sum of the three preceding ones:

Let's see the 21st element of this sequence:

(With (buffer) + + DONE && instead of ... DONE & each element of the sequence would be written to a new line.)

More complex arithmetic relationships between the last three elements can be addressed with the help of WHISK -- for instance, let's say we want each new element of the sequence to be the weighted sum of its three predecessors, the oldest one counting one fourth, the next one half, and the last one its full value.

Anything would remain as in the above script, only the line where the new element is calculated would then be:

(buffer) WHISK 4 / A 2 / B + + DONE &

(After WHISK we are left with the third last value, we divide it by 4, then A represents the first value we have removed which is the second last in the sequence so far, we divide it by 2, then B represents the last value, then the two plus operators add up the three arguments, and finally DONE gets rid of all the previous elements which (buffer) has inserted into the calulation line.)

And our result would be

  0 0 1 1 1.5 2.25 3.25 4.75 6.9375 10.125 14.78125 21.578125 31.5 45.984375 67.12890625 97.99609375 143.056640625 ...

= 1'384.53356933594

The most flexible way to base the next element of a generalized Fibonacci sequence on more than two predecessors is by using variables and the ITEM operator, though.

The script that uses this method for the "weighted sum" task above would look like this:

(At the start of the loop $a = (buffer) -3 ITEM references the first item in the list with a negative index -- while this would usually end the loop this doesn't happen here, because for the first pass of the loop Hypatia makes an exception to that rule.)

With three lines more we get the same result as above, but there are two advantages: first, it's easier to understand what the script does, and second, it allows us to perform any operations whatever with the three values (and third, we could even have more than three elements ...).

Or, we could do away with all the fancy WHISK, DONE and ITEM stuff, and just use variables:

If the sequence, as in our example, includes floating point numbers this would even be slightly more accurate, because numbers written to hy or the buffer cannot have more than 15 significant digits. Also, particularly with long sequences, this method is faster.

So why have I even shown the other methods that involve items from the result buffer, WHISK, ITEM and DONE?

To show off, of course. :)

And to show that Hypatia allows you to solve problems in different ways -- often the best solution will be the one that you will think of first and that will appear to be the easiest to write and understand.

And the more of Hypatia's features you are familar with, the more problems you will be able to solve, and the easier it will be.

If you have any questions, please ask them!

Home, Up: Loop and Script Examples, Prev: Loop Example: Monte Carlo Experiments, Next: Appendix