Recipe 19-1: The Fibonacci Sequence
The Fibonacci Sequence is a very simple sequence of integers, where the value of each number in the sequence is calculated as the sum of the previous two numbers. It is traditionally started off with 0 and 1, so if F(0) is 0, and F(1) is 1, then F(2) is F(0) + F(1), which is 1. F(3) is F(1) + F(2), which is 2. F(4) is 3, F(5) is 5, F(6) is 8, F(7) is 13, and F(8) is 21. This number sequence gets bigger quite rapidly, so apart from being a rather aesthetically pleasing sequence, it is also a useful way to look at three different methods of doing calculations using large numbers with the shell.
The concept of continuing to add two numbers together is incredibly simple, but it is remarkably ubiquitous. Figure 19-1 shows the spiral that results from the way that the Fibonacci Sequence works. Each square has sides of the length of that position in the sequence, so the first two squares are 1×1, then a 2×2 square, then 3×3, 5×5, 8×8, 13×13, 21×21, and so on. By drawing a quarter-circle in each square, a spiral emerges. This spiral can be seen in nature, from pineapples to snail shells to sunflowers.
The main pitfall when dealing with large numbers is that the storage will “wrap around” itself. Computers use base 2 internally, where a ...