Skip to main content

Module big

Module big 

Source
Expand description

§Chapter 11.3 — Natural numbers for the decimal conversions

§Purpose

The decimal conversions of Chapter 11.4 are exact: a double-double is a dyadic rational M · 2ᴱ whose decimal expansion is finite, and a decimal string is a rational D · 10^q. Both need integers of a few thousand bits and five operations on them. This module is that and no more — it is not a general big-integer library (no dependency is allowed at run time, and none is needed).

§Notation

A natural number N = Σ dᵢ βⁱ is held as its digits dᵢ in base β = 2³², least significant first. bits(N) is the position of its leading one bit plus one (bits(0) = 0).

§Algorithms

All are the schoolbook ones (Knuth, TAOCP vol. 2, §4.3.1), linear or quadratic in the number of digits.

Algorithm Q (short quotient). Input N, D > 0 with ⌊N/D⌋ < 2¹²⁸. Output (⌊N/D⌋, N mod D ≠ 0).

Q1. R ← N, q ← 0, k ← max(bits(N) − bits(D), 0). Q2. For i = k, k−1, …, 0: if D · 2ⁱ ≤ R, set R ← R − D · 2ⁱ and bit i of q. Q3. Return (q, R ≠ 0).

Binary long division: k + 1 comparisons and at most as many subtractions of numbers of bits(N) bits. The conversions call it with k ≤ 66.

§Invariants

(N1) Normalized. The most significant digit stored is nonzero; zero is the empty digit string. Nat::check_invariants (test builds).

§References

Knuth, TAOCP vol. 2, §4.3.1 (Algorithms A, S, M) and §4.4 (radix conversion).

Structs§

Nat 🔒
A natural number (the chapter).

Constants§

BILLION 🔒
10⁹, the largest power of ten below 2³².

Functions§

low32 🔒
The low 32 bits of x.