Shell Scripting: Expert Recipes for Linux, Bash, and More

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.

Technologies Used

• Functions
• ((count++))
• $(( x + y ))
• [ x -lt y ]
• expr
• bc

Concepts

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.

Figure 19-1

Potential Pitfalls

The main pitfall when dealing with large numbers is that the storage will “wrap around” itself. Computers use base 2 internally, where a ...