Fibonacci Calculator

The precision cliff at F(79)

A JavaScript number holds integers exactly up to 2⁵³ − 1, which is 9,007,199,254,740,991. Fibonacci numbers pass that between F(78) and F(79).

F(79) is 14,472,334,024,676,221 and comes out right, because it happens to be representable. F(80) is 23,416,728,348,467,685 and a double returns 23,416,728,348,467,684 — off by one, silently, with no error and no warning.

From there the errors grow. Any tool that reports F(100) as 354224848179262000000 rather than 354224848179261915075 is showing you a rounded double, and the trailing zeros are the giveaway.

Both indices are presets on this page so the difference can be seen rather than taken on trust.

How it is computed

The obvious method adds its way up: F(2), then F(3), and so on. For F(5000) that is five thousand additions of numbers a thousand digits long.

Fast doubling gets there in about thirteen steps. Two identities do the work: F(2k) = F(k)×(2F(k+1) − F(k)) and F(2k+1) = F(k)² + F(k+1)². Each step halves the index, so the cost grows with the number of bits rather than with the index.

Binet’s formula — F(n) = (φⁿ − ψⁿ)/√5 — is the closed form, and it is a poor way to compute. It needs irrational arithmetic, and rounding error overtakes it around n = 70, well before the recurrence has any trouble at all.

The suite checks fast doubling against a plain addition loop for every index up to 500, so the clever method is verified against the obvious one rather than against itself.

The golden ratio

Divide any Fibonacci number by the one before it and the answer creeps towards φ = 1.6180339887…, the golden ratio.

It converges quickly. 8/5 = 1.6, 13/8 = 1.625, 89/55 = 1.61818…, and by F(30)/F(29) the first eleven digits are right. The page reports the ratio and how far it still is from φ.

The reason is Binet’s formula. F(n) is a difference of two powers, and the second, ψⁿ with ψ ≈ −0.618, shrinks towards zero. What is left is essentially φⁿ/√5, and consecutive terms of that have a ratio of exactly φ.

The convergence alternates: the ratio sits above φ, then below, then above, closing in from each side.

Identities worth knowing

Cassini’s identity. F(n)² − F(n−1)F(n+1) is always exactly 1 or −1, alternating. It is the basis of a classic dissection puzzle that appears to turn a 64-square area into 65 — the missing square is that ±1.

The running total. F(0) + F(1) + … + F(n) = F(n+2) − 1. The sum of a stretch of Fibonacci numbers is always one less than a Fibonacci number.

Consecutive terms are coprime. gcd(F(n), F(n−1)) = 1 always, which is why the ratio never simplifies. More generally gcd(F(m), F(n)) = F(gcd(m, n)), which is a much stronger and stranger statement.

Divisibility follows the index. F(n) is divisible by F(m) exactly when n is divisible by m. Every third Fibonacci number is even, because F(3) = 2.

Where it is real, and where it is not

The sequence does turn up in biology, and it turns up for a reason worth stating rather than waving at.

Real. Sunflower seed heads, pine cones and pineapples show Fibonacci counts in their spirals. The cause is the golden angle: placing each new element about 137.5° round from the last packs them without alignment gaps, and Fibonacci counts fall out of that packing. Branching patterns in some plants follow the same rule.

Not. The nautilus shell is a logarithmic spiral, but not the golden one — measured shells cluster nearer a ratio of 1.33 than 1.618. The Parthenon and the Mona Lisa are fitted with golden rectangles after the fact, by choosing where to put the edges. And Fibonacci retracement levels in trading are a convention among traders, not a property of markets.

The mathematics is remarkable enough without the decorations, and a page that repeated them would be less trustworthy about the parts that are true.

Lucas numbers

Same rule, different start. The Lucas numbers begin 2, 1 and then add: 2, 1, 3, 4, 7, 11, 18, 29.

They interlock with the Fibonacci numbers closely. L(n) = F(n−1) + F(n+1), and F(2n) = F(n)×L(n) — which is one way to see why fast doubling works.

Their ratios approach φ as well, and faster from the start, because the Lucas numbers are the other natural solution to the same recurrence. The page reports L(n) beside F(n) for that reason.

Sources and methodology

The sequence is catalogued and its identities are standard; these are the references.

• OEIS A000045 — the Fibonacci sequence, with its identities and references
• The Fibonacci Quarterly — the journal where these identities are developed
• Pascal’s Triangle Calculator — where the Fibonacci numbers appear along the shallow diagonals
• How we calculate — methodology

Method. Computed by fast doubling — F(2k) and F(2k+1) are derived from F(k) and F(k+1) — so the work grows with the number of BITS in the index rather than with the index itself: F(5000) takes about thirteen steps, not five thousand additions. Everything runs on arbitrary-precision integers, and the suite checks the result against a plain addition loop for every index up to 500, so the fast method is never trusted against itself. That engine is verified on every change against 76 hand-written assertions, including that Cassini’s identity gives exactly ±1 at every index up to 300, and that consecutive Fibonacci numbers are coprime at every index up to 400 — both would break immediately on an off-by-one in the doubling. The count and the per-case breakdown are published on the formula verification page.

Related calculators

Where this goes next:

More in Math, or browse all calculators.

Read the guide

The shallow diagonals of Pascal’s triangle sum to the Fibonacci numbers, and the Pascal’s Triangle Calculator draws them. For sequences that step or multiply by a fixed amount instead, the arithmetic and geometric pages apply.