Arbitrary-Precision Floating-Point Arithmetic

From representation to binary splitting — in ten chapters

Overview

When the standard IEEE 754 floating-point format is not precise enough — you want a thousand digits of $\pi$, you need a numerically unstable computation done right, or you must guarantee correct rounding every time — arbitrary-precision floating-point arithmetic is the answer. This series covers, systematically across ten chapters and from data structures to algorithms, the representation and arithmetic of arbitrary-precision floats, square roots and N-th roots, elementary functions, mathematical constants, and the fast series-summation method known as binary splitting.

By level

  • Introduction (1 chapter)

    Introduction to arbitrary-precision floating-point numbers

  • Basic (2 chapters)

    Representation of arbitrary-precision floats / arbitrary-precision floating-point arithmetic

  • Intermediate (3 chapters)

    Floating-point square root and reciprocal square root / high-precision elementary functions / computing mathematical constants

  • Advanced (4 chapters)

    Zimmermann's recursive square root / precision-doubling Newton's method for the N-th root / initial approximation for the N-th root / binary splitting and hypergeometric series

All chapters

Introduction (1 chapter)

  1. Chapter 1 Introduction to arbitrary-precision floating-point numbers

    The limits of IEEE 754, error analysis, condition number, when multiprecision floats are needed, and major libraries (MPFR, sangi, mpmath)

Basic (2 chapters)

  1. Chapter 2 Representation of arbitrary-precision floating-point numbers

    Mantissa, exponent, and sign; normalization; special values (inf, nan); effective bits; rounding modes

  2. Chapter 3 Arbitrary-precision floating-point arithmetic

    Addition, subtraction, multiplication, and division; correct rounding; Kahan summation; a three-argument FloatOps API; buffer reuse

Intermediate (3 chapters)

  1. Chapter 4 Floating-point square root and reciprocal square root

    Square root by Newton's method, reciprocal-square-root tables, precision doubling, building the initial approximation

  2. Chapter 5 High-precision elementary functions

    exp, log, sin, cos, tan, atan; argument reduction; Taylor series; the AGM; guaranteeing correct rounding

  3. Chapter 6 Computing mathematical constants

    π (Chudnovsky, Gauss–Legendre, BBP), e, γ (Brent–McMillan), ln 2, Catalan's constant, caching

Advanced (4 chapters)

  1. Chapter 7 Zimmermann's recursive square root

    Recursive divide-and-conquer sqrtrem, dc_sqrtrem, a three-layer isSquare filter

  2. Chapter 8 Precision-doubling Newton's method for the N-th root

    Newton iteration for $x^n = a$, precision doubling, order of convergence, implementation in arbitrary precision

  3. Chapter 9 Initial approximation for the N-th root

    Securing the precision of the double initial value, the stage before root extraction, exponent normalization

  4. Chapter 10 Binary splitting and hypergeometric series

    The $O(M(n) \log^2 n)$ of binary splitting, Chudnovsky π, Brent–McMillan γ, 4-way parallelism, the limits of NTT integration

Reading

  • Why computers can't store 0.1 exactly [Reading]

    Why binary cannot hold 0.1 exactly. From the bargain called rounding to the idea of buying back "correctness" by adding digits — multiprecision arithmetic, told with the shoulders relaxed.