Fibonacci with BigInt: when F(n) no longer fits in a number

Fibonacci looks harmless until the digits fall off the end of a JavaScript Number. I learned that by printing a table, copying F(80) into a spreadsheet, and watching the last digits turn into zeroes of shame. The sequence is exact. IEEE-754 is not. The Fibonacci generator uses BigInt so F(n) is the integer, not a nearby float.

This post is where Number dies (spoiler: around F(78)), how a tiny loop stays exact, and how the companion page is-it-fibonacci tests membership without listing the whole sequence.

The definition I actually use

F(0) = 0. F(1) = 1. F(n) = F(n-1) + F(n-2). Some posters start at 1, 1 and call that F(1), F(2). I do not fight them in a bar. I do pick a convention and stick to it in code. Randomly starts at zero. If your textbook omits F(0), your indexes are off by a mood.

The closed form (Binet) is pretty. It is also a float in disguise. I do not use Binet to emit exact terms in the browser. Rounding will betray you right when the blog comment is most smug. Addition of two previous terms is the whole algorithm.

Where Number gives up

JavaScript Number is a 64-bit float. Integers stay exact up to Number.MAX_SAFE_INTEGER, which is 2^53 − 1, or 9,007,199,254,740,991. Fibonacci terms grow fast. F(78) is 8,944,394,323,791,464. That still sits under the cap. F(79) is 14,472,334,024,228,221. That does not. If you compute the sequence with Number, F(79) and friends are nearby values, not the integers. Comparisons start lying. “Is this Fibonacci?” becomes “is this close to a Fibonacci in binary.”

I have seen n > 78 comments that treat 78 as cursed. It is not cursed. It is the last index you can store exactly in a Number if you started from 0 and added carefully. One extra term and you are in rounding land. People also hit trouble earlier if they multiply in Binet or if they convert through Math.round on a ratio.

F(100) is 354,224,848,179,261,915,075. Twenty-one digits. A Number cannot hold that. A string of digits can. A BigInt can. I print BigInt with .toString() because JSON will not serialize BigInt without help. If you dump the sequence as JSON, decide on strings up front.

The BigInt loop

Start with 0n and 1n. For each next term, next = a + b, then shift. You do not need an array if you only want the nth term. You do need an array if you want the first N terms for a table. Randomly caps N at 100 because a page of 100 exact integers is enough for teaching and for copy-paste into a test. If you need F(10000), you are writing a different program, probably not in a form input.

Do not mix Number and BigInt in the addition. 1 + 1n throws. Convert indexes as Numbers, terms as BigInts. I keep the loop index as a normal integer. The values are bigint.

Overflow is not a BigInt thing in practice here. Memory is. F(n) has about n log10(phi) digits. Fine at 100. Less fine if a user could type a million. Cap the input. Show a reason.

Is it Fibonacci?

Listing terms and comparing works for small n. For a single candidate integer, there is a nicer identity: n is Fibonacci if and only if 5n² + 4 or 5n² − 4 is a perfect square. That is the Gessel test people quote. In JavaScript you must do the squares in BigInt, then integer-sqrt, then square back and compare. A Math.sqrt on a Number is how you reintroduce the F(79) bug through the side door.

Integer square root: binary search, or Newton, on BigInts. Check s * s === m. No epsilon. If both 5n²±4 fail the perfect-square test, it is not Fibonacci. Watch n = 0 and n = 1. They are Fibonacci. I have failed those in a helper that assumed n ≥ 2.

Negative numbers: the extension exists (negafibonacci). The public tool stays on non-negative integers unless the UI says otherwise. Ambiguous blog math is how you get a support mail that says “−8 is Fibonacci why did you say no.” Pick a domain and print it.

Golden ratio talk

The ratio F(n+1)/F(n) walks toward φ. That is true and mostly useless for exact generation. If you approximate F(n) as round(φ^n / √5), you get Binet again. Cute for n = 10. Hazardous for n = 80 in IEEE floats. I mention φ on the tool page because people search for it. I do not compute the table that way.

What I use this for

Interview warmups, algorithm demos, and a reminder that “JavaScript number” is not “integer.” Pair it with the color generator if you are making a spiral visualization: colors are floats, indexes should still be exact. If you need a random integer instead of a sequence, that is a different tool.

Do not use Fibonacci as a unique id. The sequence is public and tiny at the start. Use a UUID. Do not use Fibonacci as a secret. I have seen a “hash” that was F(n) for n = user id. Please do not.

Copy-paste footguns

Spreadsheets will round 21-digit terms. Paste as text. CSV with quotes. If Excel eats F(100), that is Excel. The generator can copy a plain list or CSV. I prefer one term per line when the digits get long.

Comparing as strings without padding is fine for equality. Sorting Fibonacci strings lexicographically is not numeric sort. If you must sort big integers, compare BigInts, not UTF-8.

A worked walk to F(78)

You do not need to memorize F(78). You need a unit test that computes the sequence with BigInt and asserts F(78) equals 8944394323791464n and F(79) equals 14472334024228221n. Then assert that Number(F(79)) is not equal to that integer when compared via string. That single test documents the cliff better than a comment. I keep those two constants in the is-it-fibonacci tests as well, because the square identity must still say yes when n has 16 digits.

If you implement integer sqrt wrong, F(78) still passes (it fits in Number) and F(100) fails. That is why the membership tests should include a fat n, not only 0, 1, 2, 3, 5, 8. I also throw a non-Fibonacci like 4 and 6 and 11 at it. Off-by-one in the 5n²±4 choice tends to bless a neighbor.

People ask about Lucas numbers. Related sequence, different initial conditions. The generator does not print Lucas unless we add a toggle. Mixing them in a FAQ is how a student copies the wrong table into a crypto toy. Fibonacci only, indexes from zero, BigInt all the way down.