Computing Fibonacci Numbers

The Fibonacci sequence is one of the most famous in mathematics. It begins with what we'll call the zeroth term1, F(0)=0F(0) = 0, and F(1)=1F(1) = 1. It is then defined recursively, so F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2). It begins 0, 1, 1, 2, 3, 5, 8, 13, and so on.

How can we compute an arbitrary value of the Fibonacci series F(n)F(n) as quickly as possible? This simple-sounding question provides a fascinating look into some very important topics in math and computer science. Even though computing the 10 billionth Fibonacci number has no practical value I'm aware of, the techniques we will explore in our attempt to get there are incredibly useful and worth knowing. It's rather remarkable that such a variety of mathematics can lurk behind such a simple-sounding problem.

Let's get started!

  1. One irksome inconsistency in the Fibonacci sequence is how the terms are numbered. Some works start with F(1)=0F(1) = 0, others F(1)=1F(1) = 1 without a zeroth term, and it's just a headache all around. We'll use F(0)=0F(0) = 0 because for programming it's nice to have zero-indexing and because it lets us simply say F(n)=nF(n) = n when n≤1n \le 1.↩

Computing Fibonacci Numbers

The Fibonacci sequence is one of the most famous in mathematics. It begins with what we'll call the zeroth term1, F(0)=0F(0) = 0, and F(1)=1F(1) = 1. It is then defined recursively, so F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2). It begins 0, 1, 1, 2, 3, 5, 8, 13, and so on.

How can we compute an arbitrary value of the Fibonacci series F(n)F(n) as quickly as possible? This simple-sounding question provides a fascinating look into some very important topics in math and computer science. Even though computing the 10 billionth Fibonacci number has no practical value I'm aware of, the techniques we will explore in our attempt to get there are incredibly useful and worth knowing. It's rather remarkable that such a variety of mathematics can lurk behind such a simple-sounding problem.

Let's get started!

  1. One irksome inconsistency in the Fibonacci sequence is how the terms are numbered. Some works start with F(1)=0F(1) = 0, others F(1)=1F(1) = 1 without a zeroth term, and it's just a headache all around. We'll use F(0)=0F(0) = 0 because for programming it's nice to have zero-indexing and because it lets us simply say F(n)=nF(n) = n when n≤1n \le 1.↩