About Fast and Slow
Every Fibonacci number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, 21… This page works out the same one, F(n), four different ways and races them. They always get the same answer. What changes, enormously, is how much work it takes.
RACE: pick n (type it, up to 1,000,000, or use the buttons), tick the lanes you want, press RUN. Each lane runs in its own background worker, so they really do run side by side and the page never freezes. The board shows the time, the work counted (calls, additions or doubling steps) and the answer: the whole number if it is short, otherwise its first and last digits and how many digits it has. A very quick method is run many times and the time averaged, since one run is too short for the clock. Naive recursion gives up after the time you choose and says how long it would have needed. STOP ends a race early.
CALL TREE draws every call naive recursion makes for a small n, in the order it makes them: NEXT for one call or return, START to watch (PAUSE stops it, RESUME carries on). A call that works something out a second time is outlined in red, and the tally shows how often each one was worked out. Switch to MEMOISED to see the same tree with a notebook: each answer is worked out once and looked up after that.
GROWTH plots the work against n on a scale where each line up is ten times more. Drag the speed slider to give your computer a thousand or a million times the speed, and see how little further the naive method gets.
THE STORY
The numbers are named after Leonardo of Pisa, later called Fibonacci, whose book Liber Abaci (1202) asked how many pairs of rabbits there would be after a year if every grown pair has a new pair each month. Indian scholars had met the same sequence centuries earlier, counting the rhythms of poetry made of long and short syllables.
The word memoisation was coined by Donald Michie in a 1968 paper in Nature, "'Memo' functions and machine learning": a function that keeps a memo of the answers it has already worked out. Michie is the same researcher who built the matchbox machine that learns noughts and crosses, MENACE, which has its own app on this site.
The fast way rests on old identities: raise the matrix [[1, 1], [1, 0]] to the power n and F(n) appears inside it, and squaring a matrix again and again reaches a high power in a handful of steps. Edsger Dijkstra wrote the doubling formulas down as a short note in 1978 (EWD654, "In honor of Fibonacci"). Fast doubling is the same idea with the matrix taken out.
The page grew from the Python scripts FibonacciTime.py, FibSpeedTest100k.py, FibTime10AvgBest.py and FibTim10AvFil.py. They use the simple loop to time a computer: how many Fibonacci numbers can it make in a thousandth of a second, in one or two seconds, or how long does it take to make 200,000 of them, averaged over ten or twenty tests, with the best results for a phone, a tablet and a laptop listed underneath. This page turns the question round: keep the computer and change the method.
HOW IT WORKS
Naive recursion follows the definition word for word: to get F(n), get F(n − 1) and F(n − 2) and add them. Each of those asks for two more, and nothing is remembered, so F(n) takes exactly 2·F(n + 1) − 1 calls. That grows by about 1.618 (the golden ratio) for every 1 added to n: F(40) takes 331 million calls, F(80) about 76 thousand million million. This is exponential growth. It runs on ordinary numbers, since it never gets far enough to need big ones; and for a big n, which would nest calls deeper than a browser allows, it keeps its own list of calls still to make.
Memoised recursion is the same code with a notebook: before working F(k) out, look it up; after working it out, write it down. Now each one is worked out once, and the calls drop to 2n − 1. The catch is memory: the notebook keeps every Fibonacci number up to n, and they get long (F(n) has about 0.209·n digits), so for n = 1,000,000 it would hold about 43 gigabytes. Here it sits out above n = 20,000. (It runs on a stack of its own, so it can go deeper than a browser normally lets a function call itself.)
The loop keeps just the last two numbers and adds them, n times: linear work and almost no memory. It is the method of the original scripts.
Fast doubling uses F(2k) = F(k)·(2F(k + 1) − F(k)) and F(2k + 1) = F(k)² + F(k + 1)². Reading n in binary from the top, each step doubles how far it has got (and adds one when the binary digit is 1), so a million needs only 20 steps: logarithmic work.
Counting steps is not the whole story. For big n the numbers have thousands of digits, and adding or multiplying them takes longer the longer they are. That is why the loop takes seconds for F(1,000,000) though it is "only" a million additions, while doubling, with 20 steps of very large multiplications that the browser does cleverly, takes a few milliseconds. Times depend on your computer and browser; the counts do not.
FURTHER WATCHING AND READING