Big integers, floating point and precision

Every number type keeps a limited precision, and the bugs come from forgetting where the limit is. A signed 32-bit integer stops at 2,147,483,647 and a 64-bit one at about 9.22 × 10¹⁸; past that, Java and Go wrap around without an error, and C++ makes signed overflow undefined. Big integers grow as needed: Python’s int, Java’s BigInteger, Go’s math/big and JavaScript’s BigInt compute 100! exactly, at a cost in speed. Floating point stores numbers in binary with about 15 to 17 significant decimal digits, so 0.1 + 0.2 is 0.30000000000000004. Compare floats with a tolerance, add many of them with math.fsum, and keep money as whole cents or paise.

How far each type goes

Pick the type from the largest value the problem can produce, not from the inputs alone. A sum of 10⁵ values up to 10⁹ reaches 10¹⁴, past 32 bits; a product of two values up to 10⁹ reaches 10¹⁸, just inside 64 bits; and factorials pass both limits quickly:

import math
import sys

INT32_MAX, INT64_MAX = 2**31 - 1, 2**63 - 1

f = 1
for n in range(1, 26):
    previous, f = f, f * n
    if previous <= INT32_MAX < f:
        print(f"{n}! = {f:,} is the first factorial past the 32-bit limit {INT32_MAX:,}")
    if previous <= INT64_MAX < f:
        print(f"{n}! = {f:,} is the first factorial past the 64-bit limit {INT64_MAX:,}")
    if float(previous) == previous and float(f) != f:
        print(f"{n}! is the first factorial a float cannot hold exactly: {float(f)!r}")

wrapped = (math.factorial(21) + 2**63) % 2**64 - 2**63  # what a 64-bit signed multiplication keeps
print(f"21! wrapped into a signed 64-bit integer: {wrapped:,}")
print(f"100! has {len(str(math.factorial(100)))} digits, computed exactly")

try:
    print(len(str(10**5000)))
except ValueError as error:
    print("str(10**5000) raises ValueError:", error)
sys.set_int_max_str_digits(0)  # 0 lifts the limit for this program
print(f"after sys.set_int_max_str_digits(0): {len(str(10**5000))} digits")

13! = 6,227,020,800 is the first factorial past the 32-bit limit 2,147,483,647
21! = 51,090,942,171,709,440,000 is the first factorial past the 64-bit limit 9,223,372,036,854,775,807
23! is the first factorial a float cannot hold exactly: 2.585201673888498e+22
21! wrapped into a signed 64-bit integer: -4,249,290,049,419,214,848
100! has 158 digits, computed exactly
str(10**5000) raises ValueError: Exceeds the limit (4300 digits) for integer string conversion; use sys.set_int_max_str_digits() to increase the limit
after sys.set_int_max_str_digits(0): 5001 digits

// A Number is a 64-bit float: integers are exact only up to Number.MAX_SAFE_INTEGER = 2^53 - 1.
console.log(`Number.MAX_SAFE_INTEGER = ${Number.MAX_SAFE_INTEGER}`);
console.log(`2 ** 53 + 1 === 2 ** 53: ${2 ** 53 + 1 === 2 ** 53}`);

let exact = 1n;
let approx = 1;
for (let n = 1; n <= 25; n++) {
  exact *= BigInt(n);
  approx *= n;
  if (BigInt(approx) !== exact) {
    console.log(`${n}! is the first factorial a Number gets wrong: ${approx} instead of ${exact}`);
    break;
  }
}

let f = 1n;
for (let n = 1n; n <= 100n; n++) f *= n;
console.log(`100! with BigInt has ${f.toString().length} digits`);
try {
  console.log(f + 1);
} catch (error) {
  console.log(`f + 1 with a BigInt f throws a ${error.name}; f + 1n works and ends in ${(f + 1n).toString().slice(-3)}`);
}

Number.MAX_SAFE_INTEGER = 9007199254740991
2 ** 53 + 1 === 2 ** 53: true
23! is the first factorial a Number gets wrong: 2.585201673888498e+22 instead of 25852016738884976640000
100! with BigInt has 158 digits
f + 1 with a BigInt f throws a TypeError; f + 1n works and ends in 001

13! is the first factorial past the 32-bit limit and 21! the first past the 64-bit one, where a 64-bit multiplication would keep −4,249,290,049,419,214,848, a negative number with no error. A JavaScript Number is a 64-bit floating-point value, exact for whole numbers only up to 2⁵³ − 1 = 9,007,199,254,740,991, so 2⁵³ + 1 equals 2⁵³; its first wrong factorial is 23!, because the smaller ones carry enough factors of 2 to fit. Big integers have no such limit, but mixing a BigInt with a Number throws a TypeError, and CPython refuses to turn an integer of more than 4,300 digits into a string until sys.set_int_max_str_digits raises the limit, a protection against slow conversions.

Sizing works the same way for any formula. Take up to 2 × 10⁵ items with values up to 10⁹: their total reaches 2 × 10¹⁴, so it needs 64 bits, and the sum of the products of all pairs reaches about 2 × 10²⁸, which no fixed-width integer holds, so it needs big integers or an answer modulo a prime. Write the worst case down before choosing the type.

Floating point: why 0.1 + 0.2 is not 0.3

A float holds a binary fraction with 53 significant bits, a precision of about 16 decimal digits. The decimal 0.1 has no finite binary expansion, just as 1/3 has none in decimal, so the float written 0.1 is the nearest binary value, slightly above 0.1:

import math
from decimal import Decimal

print(f"0.1 + 0.2 = {0.1 + 0.2!r}, and 0.1 + 0.2 == 0.3 is {0.1 + 0.2 == 0.3}")
print(f"the float written 0.1 is exactly {Decimal(0.1)}")
print(f"math.isclose(0.1 + 0.2, 0.3) = {math.isclose(0.1 + 0.2, 0.3)}")

total = 0.0
for _ in range(10_000_000):
    total += 0.1
print(f"0.1 added ten million times with +=: {total!r}")
print(f"sum([0.1] * 10_000_000):             {sum([0.1] * 10_000_000)!r}")
print(f"math.fsum([0.1] * 10_000_000):       {math.fsum([0.1] * 10_000_000)!r}")

money = 0.0
for _ in range(1_000_000):
    money += 0.07  # a million items at 0.07 each, kept as a float
cents = 7 * 1_000_000  # the same amounts kept as whole cents
print(f"a million prices of 0.07 with +=: {money!r}; in whole cents: {cents // 100}.{cents % 100:02d}")

0.1 + 0.2 = 0.30000000000000004, and 0.1 + 0.2 == 0.3 is False
the float written 0.1 is exactly 0.1000000000000000055511151231257827021181583404541015625
math.isclose(0.1 + 0.2, 0.3) = True
0.1 added ten million times with +=: 999999.9998389754
sum([0.1] * 10_000_000):             1000000.0
math.fsum([0.1] * 10_000_000):       1000000.0
a million prices of 0.07 with +=: 70000.00000019418; in whole cents: 70000.00

The two rounding errors of 0.1 and 0.2 add up to one unit in the last place of 0.3, so == says False while math.isclose says True. Over ten million additions with += the errors pile up to 999,999.9998389754. sum() returned 1,000,000.0, since Python 3.12 adds floats with compensated summation, and math.fsum always returns the correctly rounded sum. A million prices of 0.07 added as floats came to 70,000.00000019418, while the same prices kept as whole cents added up to exactly 70,000.00. Floating point is the right tool for measurements, where 15 digits are plenty, and the wrong one for money or for counts that must be exact.

Comparing floats safely

math.isclose(a, b) returns True when abs(a − b) ≤ max(rel_tol × max(|a|, |b|), abs_tol), with a relative tolerance of 10⁻⁹ by default and no absolute tolerance. The relative part scales with the numbers, so it works for 10⁻⁶ and for 10¹⁶ alike; near 0 nothing is relatively close, so comparisons against 0 need an explicit abs_tol.

Three more tools build on these rules. Kahan summation keeps the low bits that each addition rounds away. The decimal module rounds in base 10 under rules you choose, such as half up or half even. ULPs, the gaps between neighbouring floats, give a tolerance that scales with the numbers.

Exercise and self-check

Add two numbers of up to 10⁵ digits, digit by digit, the way big-integer libraries do it inside.

def add_strings(a, b):
    """The sum of two decimal strings, as a decimal string without leading zeros ("0" for zero)."""
    raise NotImplementedError("write add_strings")

import random

from add_strings import add_strings


def test_small_sums():
    """single digits, and a sum that gains a digit"""
    assert add_strings("2", "3") == "5"
    assert add_strings("123", "877") == "1000"
    assert add_strings("0", "0") == "0"


def test_long_carry():
    """a carry that runs through every digit"""
    assert add_strings("999", "1") == "1000"
    assert add_strings("1", "99999999999999999999") == "100000000000000000000"


def test_leading_zeros():
    """leading zeros in the input never reach the output"""
    assert add_strings("007", "0003") == "10"
    assert add_strings("000", "0") == "0"
    assert add_strings("0000123", "0") == "123"
    assert add_strings("5", "05") == "10"


def test_random_against_int():
    """300 random pairs of up to 3,000 digits, against Python's int"""
    rng = random.Random(12)
    for _ in range(300):
        a = "".join(rng.choice("0123456789") for _ in range(rng.randint(1, 3000)))
        b = "".join(rng.choice("0123456789") for _ in range(rng.randint(1, 3000)))
        assert add_strings(a, b) == str(int(a) + int(b)), (a[:20], b[:20])


def test_hundred_thousand_digits():
    """two numbers of 10^5 digits"""
    assert add_strings("9" * 100_000, "1") == "1" + "0" * 100_000
    assert add_strings("1" * 100_000, "8" * 100_000) == "9" * 100_000

/** The sum of two decimal strings, as a decimal string without leading zeros ("0" for zero). */
export function addStrings(a, b) {
  throw new Error('write addStrings');
}

import { test, assert } from 'mysmartcopilot:test';
import { addStrings } from './add_strings.mjs';

/** A small seeded generator (Park and Miller), so every run builds the same numbers. */
function generator(seed) {
  const random = () => (seed = (seed * 48271) % 2147483647) / 2147483647;
  return (k) => Math.floor(random() * k);
}

test('single digits, and a sum that gains a digit', () => {
  assert.equal(addStrings('2', '3'), '5');
  assert.equal(addStrings('123', '877'), '1000');
  assert.equal(addStrings('0', '0'), '0');
});

test('a carry that runs through every digit', () => {
  assert.equal(addStrings('999', '1'), '1000');
  assert.equal(addStrings('1', '99999999999999999999'), '100000000000000000000');
});

test('leading zeros in the input never reach the output', () => {
  assert.equal(addStrings('007', '0003'), '10');
  assert.equal(addStrings('000', '0'), '0');
  assert.equal(addStrings('0000123', '0'), '123');
  assert.equal(addStrings('5', '05'), '10');
});

test('200 random pairs of up to 1,000 digits, against BigInt', () => {
  const pick = generator(12);
  const digits = (n) => Array.from({ length: n }, () => String(pick(10))).join('');
  for (let i = 0; i < 200; i++) {
    const a = digits(1 + pick(1000));
    const b = digits(1 + pick(1000));
    assert.equal(addStrings(a, b), (BigInt(a) + BigInt(b)).toString(), `${a.slice(0, 20)} ${b.slice(0, 20)}`);
  }
});

test('two numbers of 10^5 digits', () => {
  assert.equal(addStrings('9'.repeat(100000), '1'), '1' + '0'.repeat(100000));
  assert.equal(addStrings('1'.repeat(100000), '8'.repeat(100000)), '9'.repeat(100000));
});

Overflow in five languages, reproduced and caught Pro: opens with a Pro, Premium or Ultimate pass

Floating-point error measured: sums, tolerances, rounding and money Pro: opens with a Pro, Premium or Ultimate pass

Exact fractions, the JSON number trap and a practice set Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• Size the type from the largest result: 13! passes 32 bits, 21! passes 64 bits, and two values of 10⁹ multiply to 10¹⁸.
• Java and Go wrap around silently, C++ signed overflow is undefined, and a JavaScript Number is exact only up to 2⁵³ − 1.
• Big integers are exact at any size: Python’s int, BigInteger, math/big and BigInt.
• Floats carry about 15 to 17 digits: compare with math.isclose, add many with math.fsum, and keep money in whole units.