Bigints for Float People

A double (the usual 64-bit floating-point number, and every Number in JavaScript) keeps 53 significant bits, counting a hidden leading 1. Every whole number up to 2⁵³ fits exactly. Past that, the gap between neighbouring doubles is 2, then 4, then 8, and adding 1 does nothing at all.

Those 64 bits are a sign, an 11-bit exponent and a 52-bit fraction. Type any number to see how it's really stored, and the exact value hiding behind it.

A bigint (arbitrary-precision integer) is an array of machine words, called limbs. It's the grade-school picture of a number as a list of digits, with the base raised from 10 to 2³⁰ (Python) or 2⁶⁴ (the GMP library). The array grows as the number grows, so nothing is ever rounded or dropped.

• Addition goes limb by limb from the least significant end, carrying into the next limb exactly as on paper.
• Multiplication is schoolbook for small sizes, which takes k² limb products for k limbs. Libraries switch to cleverer methods as numbers grow (next section).
• Division with remainder is exact long division in base 2³⁰ or 2⁶⁴. That remainder is the workhorse of everything below.

Schoolbook multiplication of two k-digit numbers takes k² digit products, so doubling the length quadruples the work. In 1960 Andrey Kolmogorov suggested at a Moscow seminar that k² couldn't be beaten. Anatoly Karatsuba, a 23-year-old student in the room, found a way to beat it within about a week.

Split each number in half around a base B (here a power of 10):

Multiplied out, x·y = x₁y₁·B² + (x₁y₀ + x₀y₁)·B + x₀y₀. That's four half-size products. The trick is that the middle term comes from one extra product:

So three half-size products are enough. Additions are cheap, and applied again and again to the halves, the Karatsuba algorithm costs about k^1.585 instead of k² (the exponent is log₂ 3).

Karatsuba is the first rung of a ladder. GMP sticks with schoolbook below a tuned threshold (as low as 10 limbs on some processors), where its simplicity wins, then switches to Karatsuba, then to Toom–Cook (splitting into three or more pieces), then to FFT-based methods. In 2019 David Harvey and Joris van der Hoeven reached k log k, the speed Schönhage and Strassen had conjectured was the best possible back in 1971. For the 62-bit numbers in section 6, plain schoolbook is fastest: each one is only 3 limbs in Python, and a single limb in GMP. Karatsuba starts paying off somewhere from several hundred to a few thousand bits.

C's uint64_t holds 0 to 2⁶⁴ − 1. When a result is too big it doesn't round. It wraps around, keeping only the low 64 bits, so every operation is exact arithmetic mod 2⁶⁴. That's integer overflow: a different failure from floating point, and a silent one. Code that needs a product mod a prime p below 2⁶⁴ keeps the full 128-bit product first (unsigned __int128 in GCC) and only then reduces mod p. Fast factor sieves on graphics cards live on exactly this kind of word arithmetic.

Here's the real payoff. Take the Fermat number F₅₅ = 2²⁵⁵ + 1. It has 36,028,797,018,963,969 bits, or 10,845,748,610,397,182 decimal digits. Just writing it down in binary would take about 4.5 petabytes. You never need to hold it, because with modular arithmetic you can take remainders at every step:

To raise something to the power 2^m, square m times and reduce mod p after each squaring. Every value along the way stays below p, so the biggest thing ever in memory is one product of two numbers below p. For a 62-bit p that's at most 124 bits. All of it exact. If you've climbed Fermat's Ladder, this is the same trick, and F₅₅ is on its factor table.

You can check Euler's rows by hand: 256² = 65,536 = 102·641 + 154, then 154² = 23,716 = 36·641 + 640, and 640 is −1 mod 641. So 641 divides 2³² + 1.

The second table is the same recipe for F₅₅ with p = 29 · 2⁵⁷ + 1 = 4,179,340,454,199,820,289: 55 squarings of 19-digit numbers, landing on −1 at the last step.

Showing p divides the giant is half the job. The other half is showing p is really prime, and not just "probably prime". This button runs the full check with JavaScript BigInt. We also ran it separately in Python, so it's two independent implementations of the same exact arithmetic.

The last line is the Lucas primality test, and it's a proof, not a probability. Fully factor p − 1, then find a number a where a^p−1 ≡ 1 but a^(p−1)/q ≢ 1 for every prime q dividing p − 1. That means a cycles through exactly p − 1 different values mod p before repeating, so all p − 1 nonzero remainders are invertible. That only happens when p is prime. Here p − 1 = 29 · 2⁵⁷ has only two prime factors, 2 and 29, so there are just two things to check, and a = 3 works.

Some proofs need real analysis: integrals, logarithms, exponentials. There you can't stay in the integers, so careful provers carry an interval [lo, hi] that is guaranteed to contain the true value. Every operation rounds the low end down and the high end up. Rounding error can widen the interval, but it can never push the truth outside it. That's interval arithmetic, and it's how computer-assisted proofs handle real numbers honestly (Python's mpmath has it built in as mpmath.iv).