Decimal digits of π in O(√n) memory: Gourdon’s unpublished 2003 Theorem 2, reconstructed

In 2003 Xavier Gourdon announced that the n-th decimal digit of π could be found with an adjustable memory budget m instead of the usual O(log² n) — but never published how. This site reconstructs a concrete algorithm that hits his bound, implements it in Rust, and races it against the classical method live in your browser, on the same code the CLI uses.

Live demo

Race: Theorem 1 vs Theorem 2

Both lanes compute the same 10 digits, starting from the same position, using the same WebAssembly build of the code the CLI uses — one running Theorem 1 (the classical, O(log² n)-memory method), the other Theorem 2 (this reconstruction). Positions up to 200,000 are checked live against a shipped reference file.

Positions up to 2,000 are computed by the same exact fallback (pi_ref, an integer Machin sum) in both lanes, not by either theorem, so a race below 2,000 (e.g. the 1,000 preset) times identical code twice; it's kept as a preset because it's a fast, always-available sanity check, but a race above 2,000 is the one that actually compares the two theorems.

Position

Theorem 1

Elapsed: –

Time: – · Memory: –

Theorem 2

Elapsed: –

Time: – · Memory: –

Stream

Computes successive 10-digit blocks from scratch, one after another, using Theorem 1, never holding earlier digits in memory — the “keep churning” case that started this whole project.

The first ~200 blocks (positions up to 2,000) are computed by the same exact pi_ref fallback every other small position uses, not by Theorem 1's Gourdon method proper; the stream starts at 10,001 by default so it opens on Theorem 1 itself.

Start position

Memory: –

Background

The BBP formula (Bailey–Borwein–Plouffe, 1995) can produce hexadecimal (or any power-of-two-base) digits of π starting at an arbitrary position, without computing the digits before it, in roughly linear time and logarithmic memory. Nothing structurally similar is known in base 10 — decimal digits are hard for the same reason a base-10 BBP formula for π appears not to exist (see the postscript). Getting a decimal digit therefore means a different kind of algorithm: an accelerated series for π itself, truncated and manipulated so that only the digits you want fall out.

The timeline for that approach: Plouffe (1996) found a way to extract a decimal digit without storing every digit before it, at roughly cubic time. Bellard (1997) brought that down to O(n²)-ish time with O(log n) memory, no time–memory trade-off. Gourdon (2003) went further: his Theorem 1 gets a decimal digit in O(n² loglog n / log² n) time with O(log² n) memory — still effectively fixed, tiny memory, and it is the method this site's own CLI implements as its non-default method (--method thm1). His Theorem 2 is the subject of this page: the same digit, but with a memory budget m you can dial up to trade for a large speed gain. He stated it. He did not publish how.

The claim

From Gourdon's 2003 preprint (Proposition 1 gives the working formula; the paragraph on intermediate memory sizes states Theorem 2 without proof):

With a memory budget of m bits (nε ≤ m ≤ n), the n-th decimal digit of π can be computed with an O(m)-bit working set, in roughly \(O\!\left(\dfrac{n^2 \log^3 n \operatorname{loglog} n}{m \log^2(n/m)}\right)\) time. “Details of this algorithm will [be] added soon.”

That follow-up never appeared. The PDF at Gourdon's own URL is unchanged since 12 Feb 2003 (same 9 pages, same creation date); the web version's TeX source has no commented-out details either. We found no paper, thesis, program or forum post anywhere that gives Theorem 2's algorithm, or even cites it with any detail beyond the one-paragraph statement above.

What the literature has

Sources checked for any trace of Gourdon's Theorem 2
SourceWhat it contains
X. Gourdon, Computation of the n-th decimal digit of π with low memory, 11 Feb 2003. PDF: numbers.computation.free.fr (mirror: plouffe.fr, Scribd copy) Theorem 1 in full; Theorem 2 stated only. Still dated 12 Feb 2003 (PDF CreationDate), 9 pages, same text as ever. No later version exists at that URL.
nthdigit.html and its TeX source nthdigit.tex Web version of the same text. “Generalization for intermediate memory size” repeats the bound and says “Details of this algorithm will added soon in [3]” ([3] = the 2003 preprint). The TeX has no commented-out details. Generated by TTH on 12 Feb 2003.
pidec (Gourdon's program, linked from the page above) Theorem 1 only (per the paper's own timing section).
github.com/logc/pidec Racket digit extractor “based on Fabrice Bellard's paper.” Not Gourdon's Theorem 2.
F. Bellard, pi_n2.html, pi.c/pi1.c O(n²)-ish, O(log n)-memory decimal digit extraction. No trade-off.
S. Plouffe, arXiv:0912.0303 and arXiv:2201.12601 Low-memory / formula-based n-th digit. No time–memory trade-off, no Theorem 2 details.
Cheng, Hanrot, Thomé, Zima, Zimmermann, Time- and space-efficient evaluation of some hypergeometric constants, arXiv:cs/0701151 Binary splitting with O(d) space for all first d digits. Doesn't cite Gourdon and does no digit extraction. Relevant only as the “m ≈ n” end of the trade-off.
Gourdon–Sebah truncation trick / Yakhontov, arXiv:1209.5097 O(p)-space binary splitting for all digits. Same remark.

As far as we can tell, the reconstruction below is the only written version of Theorem 2's algorithm anywhere.

The reconstruction

Everything below is our own work: an algorithm we believe matches Gourdon's stated bound and is plausibly close to what he had in mind, not a recovery of his actual method (which remains unpublished). Claims are tagged proved (argued in full, either here or in the fuller write-up), measured (prototype or benchmark data), or conjecture (stated as a belief, not a proof).

The accelerated series

Start from Gourdon's Theorem 1 identity, a Cohen–Villegas–Zagier-accelerated form of π/4 = Σ(−1)k/(2k+1):

\[ S = \sum_{k=0}^{(M+1)N-1} (-1)^k \frac{4}{2k+1} \;-\; \sum_{k=0}^{N-1} (-1)^k \frac{4\,s_k}{2^N(2MN+2k+1)}, \qquad s_k = \sum_{j=0}^{k} \binom{N}{j}, \qquad |S-\pi| \le \frac{\pi}{(2eM)^N}. \]

Choosing M and N (both even, N ≤ n+2) makes every quantity in sight an ordinary machine-word modular fraction: Gourdon's Proposition 1 turns this into frac(10nπ) ≈ frac(B − C) with error < 10−n₀,

\[ B = \sum_{k<(M+1)N} (-1)^k \frac{4\cdot 10^n \bmod (2k{+}1)}{2k+1}, \qquad C = \sum_{k<N} (-1)^k \frac{X\cdot s_k \bmod m_k}{m_k}, \]

with X = 5N−2·10n−N+2 and mk = 2MN+2k+1. Theorem 1 takes M ≈ 2n/log³n, so B is cheap and C costs O(k) word operations per sk — that O(k) inner sum is exactly the cost Theorem 2 needs to beat.

Why “blocking gains nothing” doesn't hold proved

The obvious objection to any memory-budget scheme: update an m-bit accumulator one small factor at a time, and it costs O(m/w) work per factor (w = word size) — no better than doing it in full precision. That's true for naive blocking. It's false for binary splitting: the factors (N−j+1) and j in the recurrence below are small integers that don't depend on the block modulus, so g ≈ m/log n of them can be multiplied together exactly with a product tree, costing O(M(m) log m) total — polylog per factor instead of m/w — then reduced once mod the block modulus Q. With fast (subquadratic) multiplication the cost per (term, j) pair drops from Θ(1) to Θ(log n·log²m/m). With schoolbook multiplication the gain collapses to a constant, so the real requirement is subquadratic multiplication, not a cleverer accumulator.

The (P, T, D) recurrence

For target t, define state Pt = N!/(N−t)!, Dt = t!, Tt = t!·st, with (P₀,T₀,D₀)=(1,1,1). One step (1 ≤ j) is P ← (N−j+1)P; T ← jT+(N−j+1)Pold; D ← jD. A block of steps composes as a triple (α,δ,τ) acting on (P,T,D), and triples compose by standard binary splitting: (α₁α₂, δ₁δ₂, δ₂τ₁+τ₂α₁). Then st ≡ TtDt−1 and C(N,t) ≡ PtDt−1 mod q, whenever gcd(q, t!) = 1. The symmetry sk = 2N − sN−1−k halves the targets that ever need computing.

Partial fractions: main, Lucas, p-adic

The obstacle Gourdon's obstacles list raises is real: mk can be composite and share prime factors with t! (Dt stops being invertible mod mk). The fix is to factor mk = Πpe and use partial fractions, frac(Xs/m) = Σq frac(Xs·((m/q)−1 mod q)/q), handling each coprime part q by whichever of three methods is valid for it:

PartConditionMethod
mainproduct of all pe with p > t the accumulating-remainder-tree item above (target t, modulus q) — Dt is invertible here by construction
Lucasp ≤ t, p ∥ mk Lucas' theorem, reducing to one small residue mod p (below)
p-adicp ≤ t, pe ∥ mk, e ≥ 2 the p-adic Lucas recursion (below), no big numbers
Lucas' theorem, applied proved

Write digits N = ΣNipi and t = Σtipi, with Gi(x) = Σy<xC(Ni,y) mod p:

\[ s_t \equiv \sum_i \Big[\!\prod_{u>i} \binom{N_u}{t_u}\Big]\, G_i(t_i)\, 2^{\sum_{u<i} N_u} \;+\; \prod_u \binom{N_u}{t_u} \pmod{p}. \]

For i = 0, C(N₀,y) ≡ C(N,y) for y < p, so G₀(t₀) and C(N₀,t₀) both come straight from the main-item computation above. For i ≥ 1, Ni ≤ N/pi, so those rows cost O(min(p, N/p)) per prime — this is Lucas' theorem plus a lexicographic split of {j ≤ t}.

The p-adic Lucas recursion (p² case) proved

Lucas' theorem alone breaks when p2 ∣ mk: a single residue mod p isn't enough. Write N = pK+N₀ and g(x) = ((1+x)p−1−xp)/p ∈ ℤ[x]. Then

\[ (1+x)^N \equiv \sum_{i<e} \binom{K}{i} p^i\, (1+x)^{N_0} g(x)^i (1+x^p)^{K-i} \pmod{p^e}. \]

Putting hi = (1+x)N₀gi (degree < (i+1)p, with prefix sums Hi) and t = pT+r gives a recursion on rows of size ≈ N/p, depth logpN, base case N < p (fully invertible). At e = 1 this collapses back to plain Lucas. The prototype checked it against exact binomials for 400 random (p, e, N, t) cases with p ≤ 101, e ≤ 4.

The chunked accumulating remainder tree

All of this is assembled by sorting every (target, modulus) item by target and cutting the sorted list into chunks whose modulus product has ≈ m bits. Each chunk builds a product tree of its moduli, advances the (P,T,D) state to the chunk's first target by binary splitting in groups of g = ⌊m/log₂N⌋ steps, then descends the tree — at each node, the left child inherits the state mod its own modulus, and the right child's state is advanced from the left target to its own, mod its own (smaller) modulus. A leaf outputs (P,T,D) mod its item's modulus. Nothing outside one chunk's O(m)-bit working set is ever held at once. In a memory-faithful implementation, items are generated on the fly in target order via a segmented sieve, rather than built as one global list up front — this streaming construction is what crates/pi-digits/src/nthdigit2.rs's stream_needs_and_chunks implements.

Complexity proved, modulo the stated model

Model: w = Θ(log n)-bit words, and b-bit multiplication costs M(b) = O(b log b loglog b) bit operations. Summing the accumulating-remainder-tree cost, the Lucas/p-adic tables, and balancing the B and C parts of the series against each other (M = Θ(max(4, N log²m loglog m / m)), i.e. M ∝ n/m up to logs) gives:

\[ T(n, m) = O\!\left( \frac{n^2 \cdot \log n \cdot \log^2 m \cdot \operatorname{loglog} m}{m \cdot \log^2(n/m)} \right) \text{ word operations, memory } O(m \log m) \text{ bits (}O(m)\text{ with care).} \]

For m = nΘ(1), log²m = Θ(log²n), and this is exactly Gourdon's stated bound. At m = √n it gives O(n3/2 log n loglog n), his first special case. The log²(n/m) denominator is the fingerprint: it comes from N² with N ∝ n/log M and M ∝ n/m, i.e. directly from balancing B against a binary-splitting C part — the same balancing act Theorem 1 already does, just with an adjustable knob. conjecture We're fairly confident this is the algorithm Gourdon had in mind; his handling of small primes may have differed, and a loglog from Σ1/p (as in his own Lemma 1) would fit the same bound just as well.

Implementation

The certification path is not behind any abstraction seam: it is plain u128 fixed-point integer code, unchanged across bignum backends. Each term (x mod m)/m is stored as a u128 fixed-point fraction f/2128, computed by exact 128-by-64 long division, so its representation error is < 2−128 (one ulp). Terms accumulate via wrapping add/subtract, which is exact arithmetic modulo 1 on this encoding, so accumulation order never matters. The certification bound (error_units) adds one ulp per term to Gourdon's own truncation bound π/(2eM)N < 10−(n+n₀); n₀ is capped at 24, and long digit requests are split into independent chunks so no single evaluation needs more precision than that. Two cases fall outside this fixed-point loop entirely and go to an exact fallback instead, itself certified the same way (agreement across a verified bracket, guard doubled and retried on disagreement): small positions (below 2,000, where Gourdon's method doesn't apply), and a rare boundary case at any position where a long run of equal digits pushes n₀ past what the u128 accumulator can certify. Both use an exact integer Machin sum (pi_ref); the rare large-n boundary case uses MPFR instead under the native CLI's gmp backend, where it's much faster.

digits(n, count) never returns a digit it can't certify this way: it computes x = frac_10n_pi(n, n₀) with n₀ = count + guard (guard starts at 4), then re-extracts the requested digits from x, x+err and x−err. If all three agree, the digits are certified; if the true value sits too close to a run of 9s or 0s for the guard to resolve, the guard doubles and the whole computation retries.

Optimization notes: what moved the clock, and what didn't

Every item below was profiled or A/B-timed before being kept, and the dead ends are listed alongside the wins. Timings quoted in this subsection were taken on the AMD Ryzen 7 5700G (6 cores) the work was done on; the benchmark tables below were re-measured on different hardware, so don't mix the two.

  • measured Trial division was never the bottleneck. The starting assumption was that finding the prime factors of each mk by trial division dominated Theorem 1's C-sum. Instrumenting it showed the O(k) binomial loop that follows costs roughly 25–27× more (n=105: 331 ms factoring vs 8.4 s loop; n=106: 32 s vs 865 s, summed across threads). A segmented sieve replaced the trial division anyway (it's correct, cheap, and the old path stays behind a flag for the strict-O(log² n)-memory case), but on its own it was worth only the ~4% share factoring had to begin with. A first cut with one fixed segment size collapsed the whole sum into one or two parallel tasks and ran 4–5× slower at n=105; segments are now sized off N and the thread count (~32 per thread) so work-stealing can even out the per-k cost skew.
  • measured Montgomery multiplication in the hot loop. The binomial loop does a handful of multiplies against the same modulus for its whole run, which is exactly what Montgomery form is for: one cheap redc instead of a 128-bit division per multiply. This is the change that actually moved Theorem 1's wall-clock. The first attempt made things slower than plain division: it re-encoded every prime's running remainder into Montgomery form on every step. Caching each one's Montgomery form and refreshing it only when it actually changes (rare) turned it into a win.
  • measured The other hot loop (Theorem 2). The B part of the B − C split is shared by both theorems and computed 10n mod m with plain binary exponentiation over 128-bit division. Invisible while Theorem 1's C-sum dominated, it became the dominant cost once Theorem 2's chunked remainder tree made C cheap: perf put 49.6% of all CPU time in the compiler's software 128-bit divide (__umodti3) for a single-thread n=3×106 run. Switching that exponentiation to Montgomery form (same algorithm, tested against the old one on random inputs) took n=3×106 from 103.3 s to 81.7–86.1 s on one thread, and from 44.1 s to 18.0 s (~2.4×) on six: the removed work parallelised no better than what replaced it, so cutting its total mattered more once threads were fighting over memory bandwidth. The division routine vanished from the profile; the new top cost is redc itself, real multiplication rather than division.
  • measured Dead end: GMP as a hidden memory term. The memory work above tracked only Rust-side allocations; GMP's own malloc calls were invisible. Routing GMP through the same counter changed the tracked peak by exactly nothing (n=100, 3×106 and 107). The remaining gap to OS-measured RSS is a fixed process floor (~4.5 MiB for binary and shared libraries at n=100) plus, probably, worker-thread stacks.
  • measured Dead end: shrinking the product tree. The theory offered cutting the chunk budget by a log factor to bring the tree from O(m log m) down to O(m): same total work, just more, smaller chunks. At n=3×106 the chunk count went from 551 to 7,625 as predicted, tracked memory didn't improve (6.36 to 6.48 MiB), and wall time went from 44 s to 461 s. "Same total work" holds only for the variable part of the cost; the fixed per-chunk overhead (re-factoring the window, a hash map built and torn down, a task dispatched) doesn't shrink with the chunk, and ~14× more chunks made it dominate. Reverted.
  • measured Bellard's algorithm, in Rust. A port of pi.c/pi1.c with Montgomery arithmetic, batched inversion, a prime sieve and threading is ~4× faster single-threaded than the plain port. One real micro-win: making Montgomery's final conditional subtract branchless (the branch was ~50/50 and unpredictable) gave 12% on pi.c and 19–20% on pi1. Three attempts to go further all lost: a 4-lane AVX2 version ran 7–8% slower (perf traced it to the compiler spilling the loop-carried vectors to the stack every iteration, with 11 of 16 YMM registers unused, and four different source-level fixes produced the identical spill); vectorising the batched-inverse extraction ran ~29% slower (it needs a gather, not a contiguous load); and hand-written assembly was scoped out as too risky for an ~8% gap. All still O(n²).

The memory story at n = 10⁷

Four implementation stages, same position, same machine (the Ryzen 7 5700G the work was done on, not the machine used for the benchmark tables), peak resident memory:

  • measured 812.1 MiB — the first port: a full O(N) factorisation table and a full sorted item list, held before any chunk ran.
  • 447 MiB (reported, not re-measured here) — after streaming item generation removed the global tables, generating chunks on the fly. This is the task brief's own figure for that intermediate stage; see docs/nthdigit.md for why it wasn't separately re-derived.
  • measured 69.2 MiB — after a memory-profiling pass found the streamed version's real remaining cost wasn't where its own docs blamed it: a p-adic recursion memo table that leaked across an entire prime's worth of queries instead of clearing between them (roughly 40 of 58 MiB at n=10⁶ on its own), and small-prime need-lists that stored every matching (k,t) pair instead of the compact arithmetic-progression range each one actually forms. Both fixed.
  • measured ~20–24 MiB (two runs) — after bounding the one piece that stage still left genuinely O(N): each target's leftover-prime cofactor need (below). Resolved in fixed-size batches as they're found instead of collected for the whole run before any of them are resolved.

Each target's cofactor — the single leftover prime factor of mk above √(max mk), when there is one — needs the same Lucas treatment as a small sieve prime, but is essentially unique to its own k (or its mirror), not shared by a residue-class arithmetic progression, so it resists the same per-prime compaction the small primes got. Grouping doesn't shrink it; bounding how many are ever alive at once does: they're now resolved in batches sized off the memory budget itself, each batch folded into a running total and discarded, rather than collected into one structure that grows with n for the whole run. Wall-clock time was unchanged within run-to-run noise at every n tested.

Benchmarks

measured All numbers in this section were measured on one machine on 2026-10-08: an AMD Ryzen AI 9 HX 370 (12 cores / 24 threads, boost to 5.16 GHz), 62 GiB RAM, Linux 7.2 with the CPU governor left on powersave, release builds (rustc 1.98.1; gcc 16.2.1 -O3 -march=native for Bellard's C). Time is wall-clock and memory is peak resident size, both read from the CLI's own instrumentation; each cell is the fastest of 2–3 runs (one run for Theorem 1 at 107, 55 minutes), with the sleep inhibited so nothing suspended mid-run. Theorem 2 uses all 24 threads; Theorem 1 is the same code path Gourdon's method describes, run through the same CLI. This is a laptop-class part, so run-to-run spread was up to ~25% at the larger positions (thermals, boost state). The earlier historical pidec (2003 Pentium III) column has been dropped: its source is no longer available to re-run on this hardware, and numbers from a different machine and era don't belong in this table.

Wall-clock time vs digit position (log–log)
10,000100,0001,000,00010,000,00010 ms100 ms1 s10 s100 s1,000 s10,000 sDigit position nWall-clock timeTheorem 1Theorem 2
Peak memory vs digit position (log–log)
10,000100,0001,000,00010,000,0001 MiB10 MiB100 MiBDigit position nPeak memory (MiB)Theorem 1Theorem 2
Benchmark table: time and memory for Theorem 1 and Theorem 2
Position n Theorem 1 time Theorem 1 memory Theorem 2 time Theorem 2 memory
10,00015 ms5.0 MiB16 ms7.5 MiB
100,000686 ms5.1 MiB194 ms10.4 MiB
1,000,00050.8 s6.0 MiB3.04 s20.0 MiB
3,000,000——13.9 s31.1 MiB
10,000,0003,283 s (54m 43s)11.5 MiB82.5 s (1m 22s)46.7 MiB

Theorem 2's memory grows with position (it's spending memory to buy speed — though as of the cofactor-batching fix above, a fair amount of what used to grow here was implementation overhead, not the deliberate trade). Theorem 1's stays at a few MiB, about 5 to 6 through 106; its 11.5 MiB at 107 is the factoring sieve, which grows like the square root of the position, plus a larger thread pool than the older machine, not a break from the O(log² n) core. The two methods are level at 10,000 (15 vs 16 ms, inside noise); Theorem 2 is faster from 20,000 up, by a growing margin: about 1.2× at 20,000, 3.5× at 100,000, 17× at 1,000,000 and 40× at 10,000,000. The Theorem 2 numbers include the Montgomery fix to the shared B part described above, so they are not comparable to the earlier 5700G figures (which predate it).

Other existing algorithms: Bellard's pi.c / pi1.c (1997)

measured Every comparison above is this site's own two methods plus one unreproducible historical baseline. Fabrice Bellard's 1997 pi.c is a different author's implementation of a different algorithm: a refinement of Plouffe's 1996 any-base n-th-digit method down to O(n²) time, O(log n) memory; pi1.c is a ~4× faster variant of the same algorithm using Gosper's series. Both re-measured here, same machine as the table above (gcc 16.2.1 -O3 -march=native, one thread):

Benchmark table: Theorem 1, Theorem 2, and Bellard's pi.c/pi1.c
Position n Theorem 2 Theorem 1 pi1.c (Gosper) pi.c
10,00016 ms15 ms2.49 s6.67 s
20,00040 ms48 ms7.57 s25.6 s

All four agree on digits at both positions — a free correctness cross-check, since pi.c/pi1.c are a completely independent implementation of a completely independent algorithm. The table stops at 20,000: O(n²) puts pi.c at roughly 2½ minutes by n = 50,000 (extrapolated from the 20,000 row), and the gap only widens from here — Theorem 1 (the same O(n²) class, just a different formula) shows the same widening trend against Theorem 2 in the table above out to 10,000,000. See research/bellard/ in the source for the full methodology, a Rust port with a threaded/Montgomery-arithmetic variant (still O(n²) — same conclusion, faster constant), and pi_bin.c, our own implementation of bellard.org/pi's n-th binary-digit formula (a different base, not comparable to the table above).

Verification

Position convention

Two conventions coexist and are easy to conflate: the CLI's pihunt digit <pos> is 1-based (position 1 is the first digit after the decimal point); the library functions (nthdigit::digits, nthdigit2::digits) return positions n+1 ..= n+count, so the CLI calls them with n = pos − 1. Every digit string on this page is a CLI position.

Digits at each CLI position, and at position+1, for cross-checking the convention
pihunt digit positiondigitsposition + 1
10485667227965667227966
10564126002434126002437
10613092756283092756283
3·10636970679156970679155
10772591513362591513361

10⁴–3·10⁶ regenerated with the CLI on 2026-09-23, Theorem 1 and 2 agreeing; 10⁷ both columns MPFR-verified.

MPFR agreement

measured Both theorems' digits are checked against MPFR (via rug) at positions 10⁴, 10⁵ and 10⁶, and independently cross-checked with a second binding, gmpy2's const_pi, at 10⁶ and 10⁷. All agree, and Theorem 1 and Theorem 2 agree with each other at every position tested, including the Feynman point (position 762, a run of six 9s) and hundreds of sequential and random positions up to 20,000 and beyond, across multiple memory-budget settings for Theorem 2. The full pi-digits suite runs a second time with a completely independent pure-Rust bignum backend (no GMP), still checked against MPFR, to catch anything backend-specific.

Browser checks

The race panel above compares the two WebAssembly lanes directly and flags any disagreement; for positions up to 200,000 it also checks the result against a shipped reference file (pi-200k.txt), independently generated and MPFR cross-checked, marking each run ✓ or ✗.

Errors we caught

Three real mistakes surfaced during this work, in the interest of being honest about how this reconstruction was actually built:

  • A missing rounding term in the certification bound. An earlier version of the error budget omitted the one-ulp-per-term fixed-point rounding contribution. It was only unsound for n₀ ≳ 28 — long --count requests or a pathological boundary retry — caught in review and fixed.
  • Doc position labels mixing the CLI and library conventions. One session briefly relabelled the 107 row as 2591513361. That value is correct too — it's pihunt digit 10000001, the library call at n=10,000,000, one position later than every other row — but nothing was wrong in the code, only the label. Both 107 strings are MPFR-verified (see the table above).
  • A verification script that used int() on gmpy2 floating-point values, which rounds to the nearest integer rather than truncating toward zero. A digit-extraction check built on that assumption can silently read off the wrong last digit at a rounding boundary; fixed by truncating explicitly instead of relying on gmpy2's int().

Limits and caveats

  • measured Memory is close to but not the strict O(m) the bound promises in the asymptotic sense: the ART's own product tree is kept in full per chunk (O(m log L) rather than O(m) — recomputing nodes instead of keeping them would close that gap but isn't implemented), and there's some constant per-thread/rayon overhead this doesn't itemise. The cofactor term that used to be the dominant O(N) piece is now itself O(m), resolved in memory-budget-sized batches. None of this has been tested at, say, n = 10⁹.
  • This is a reconstruction and a verified implementation, not a formal proof that it matches Gourdon's own method, and not a claim that his proof (which we've never seen) looked like this one.
  • conjecture That this is close to Gourdon's own unpublished algorithm is a belief, not a fact — it's unknowable without his notes. What's provable is that this algorithm achieves his stated bound.
  • The p-adic tables are O(p) words in principle, with p reaching √(2(M+1)N); in practice p-adic treatment only ever applies to primes ≤ √(max mk), so the measured peak is far smaller than the theoretical worst case.

Reproduce it

This all lives in the pihunt source tree (github.com/grantstephens/pihunt), in crates/pi-digits/src/nthdigit.rs (Theorem 1) and crates/pi-digits/src/nthdigit2.rs (Theorem 2). Theorem 2 is the CLI's default method.

git clone https://github.com/grantstephens/pihunt
cd pihunt
cargo build --release

# Theorem 2 (default)
pihunt digit 1000000

# Theorem 1, for comparison
pihunt digit 1000000 --method thm1

# full test suite
cargo test --release -j 4

Postscript: the base-10 BBP hunt

Before this, the same tooling searched for a base-10 BBP-type formula for π — a series that would give decimal digits as directly as BBP gives hex ones. Over two thousand candidate shapes were searched with PSLQ across bases 10, 100 and 1000, with degrees up to 3 and extra constants (log 2, log 3, log 5, π², Catalan's constant, ζ(3)); every candidate relation was re-verified at twice the search's working precision. Nothing was found. Degree-1 (Machin-type) formulas for π are already excluded in any base that isn't a power of two (Borwein, Borwein & Galway, 2004), and higher-degree columns are periods of higher weight than π itself — conditionally on a standard, unproved conjecture about weights of periods, any relation would have to reduce to a degree-1 one anyway, which is already ruled out. So the search's null result is what the weight argument predicts, not a surprise waiting to be overturned by more CPU time. Stated plainly, the degree-1 exclusion itself is not fully checked either: it's unverified whether the Borwein–Borwein–Galway theorem covers every degree-1 BBP shape or only the Machin-type subfamily. That's the closed finding that pointed this project at attacking the cost of existing decimal digit extraction instead — which is what Theorem 2 is.

References

  • X. Gourdon, Computation of the n-th decimal digit of π with low memory, 11 Feb 2003. PDF.
  • F. Bellard, Computation of the n'th digit of pi in any base in O(n²).
  • S. Plouffe, arXiv:0912.0303; arXiv:2201.12601.
  • Y. Cheng, G. Hanrot, E. Thomé, E. Zima, P. Zimmermann, Time- and space-efficient evaluation of some hypergeometric constants, arXiv:cs/0701151.
  • V. Yakhontov, arXiv:1209.5097.
  • D. Bailey, P. Borwein, S. Plouffe, On the Rapid Computation of Various Polylogarithmic Constants, Math. Comp. 66 (1997) — the BBP formula.
  • J. Borwein, P. Borwein, W. Galway, Finding and excluding b-ary Machin-type BBP formulae, Canad. J. Math. 56 (2004).