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 below2³².
Functions§
- low32 🔒
- The low 32 bits of
x.