Home/Modules/pi-generator

pi-generator

system module pi-generator

Pi Generator

A complete, concise SLeeLa program that computes the decimal digits of Pi and streams them to a local file.

Native IPC status and reference worker

The separate Native IPC reference worker and its 20,000-digit correctness fixture are documented here:

Important distinction: the 20,000-digit IPC fixture currently runs the Python reference worker. It is not a measurement of this SLeeLa Pi generator, the SLeeLa VM math kernel, or sleelactl performance.

Algorithm

The source declares #sleela 2.9 so it is accepted by both the older Sleelvac™ compiler (supported range 1.0 – 2.9) and the current SLeeLa™ Language/Runtime build (1.0 – 3.1). It uses no 3.0-only syntax — only integer arithmetic, int[], while, and the openFile/write/close file API, all available in 2.x.

It uses the Rabinowitz–Wagon spigot, which emits Pi's digits one at a time using only bounded integer arithmetic over a single int[] array. That matters here: SLeeLa's runtime has no working arbitrary-precision/bignum type (the widest genuine integer is 128-bit), so a method that needs no big-integer type is the right fit. Digits are written to the file in fixed-size chunks via openFile / write / close, so memory stays flat instead of building one enormous string.

Run it

# from the repository root, with the source-built compiler
impl/build/sleela run pi-generator/PiGenerator.sleela
# or the prebuilt toolchain (supports syntax 1.0 – 3.1):
working-binaries/sleela run pi-generator/PiGenerator.sleela

To validate quickly, lower DIGITS (e.g. 1000 or 10000) and run again — a small count finishes in seconds and the file begins 3.14159….

Verified correct

The output was checked against an independent reference (Chudnovsky via Python decimal) and matches exactly:

Honest performance note (please read)

The DIGITS constant ships at 1,000 so the program runs to completion out of the box. The algorithm is correct at any digit count, but a very large target such as 7,000,000 will not complete in practice on this VM — not because of memory (see Version 2.0 below), but because of raw interpreter speed:

main() still guards the array against SL_MAX_ARRAY_LEN and caps gracefully (rather than dying with a raw allocation error) for any future target that would exceed even the raised ceiling.

In other words: the program is a faithful, correct Pi-to-file generator. To produce a file within a reasonable time with this algorithm, keep DIGITS in the reachable range (hundreds to a few thousand). For a much faster generator that does the heavy arithmetic in the native big-integer kernel, see PiMachin.sleela and the comparison in Version 2.0 below.

Performance — Version 2.0

Version 2.0 reflects the VM limit raise (SL_MAX_ARRAY_LEN 2²⁴ → 2²⁵ = 33,554,432 cells, and the GC byte limit 512 MiB → 1 GiB). The headline change from v1.0: allocation is no longer the wall. A 7,000,000-digit run needs a 23,333,334-cell state array (~712 MiB of boxed cells); on v1.0 that was refused (array allocation failed), on v2.0 it allocates immediately. The remaining limit is compute time.

Measured spigot runtime (v2.0)

Timed with the source-built compiler (impl/build/sleela) on this machine; the spigot is O(digits²), so time grows ~100× for each 10× in digits:

Decimal digitsState array (cells)Wall timeNotes
1,0003,334~2 smatches the reference exactly
2,0006,667~4 s
4,00013,334~9 s
10,00033,334~48 s
100,000333,334~1.3 h (est.)extrapolated, O(d²)
1,000,0003,333,334~5.6 days (est.)extrapolated
7,000,00023,333,334~272 days (est.)allocates on v2.0; does not finish in practice

The fit is clean: the implied exponent across the measured points is ~2.0 (e.g. 1,000 → 10,000 digits is 10× the work and ~24× the time once array sweeps dominate). Extrapolations use t ≈ (48 s) · (digits / 10,000)² anchored at the 10,000-digit point.

Takeaway. v2.0 makes a 7,000,000-digit array allocatable, but the O(d²) spigot would take roughly nine months of continuous computation to finish it — so it is not a practical way to reach millions of digits.

Faster: PiMachin.sleela — native big-integer kernel

The companion program computes Pi with Machin's formula

pi = 16·arctan(1/5) − 4·arctan(1/239),   arctan(1/x) = Σ (−1)ᵏ / ((2k+1)·x^(2k+1))

carried as a scaled base-1,000,000,000 integer and driven by the native big-integer opcodes — bigmul (OP_BIGMUL, NTT/Karatsuba), bigadd (OP_BIGADD), and bigdivmod (OP_BIGDIVMOD, divide by a small integer). Every per-term division (by x² and by 2k+1) is one native C long-division over the whole limb array instead of an interpreted per-element sweep.

Measured, v2.0, same machine — verified digit-for-digit against an independent reference:

DigitsSpigot (PiGenerator)Machin (PiMachin)Speed-up
1,000~2 s<1 s—
10,000~51 s~3 s~17×
20,000~200 s (est.)~11 s~18×
40,000~13 min (est.)~40 s~20×

Honest limit. PiMachin is still O(digits²) — it runs ~digits series terms and the accumulate step copies the limb array each term. It is a large constant-factor win (the heavy divides are native), not a better exponent, because in v2.0 the VM kernel exposed only bigmul / bigadd / bigdivmod (small divisor). A truly sub-quadratic method (Chudnovsky with binary splitting) needs a native big ÷ big division and a big square root — which Version 3.0 adds.

Performance — Version 3.0

Version 3.0 adds the native big-integer primitives that binary-splitting Chudnovsky needs, and a generator that uses them. New VM opcodes (see NATIVE.ADD.md for the full roadmap):

Plus a GC fix: OP_NEWARRAY now runs a full root-aware collection and retries once when the live-array table is full, so the allocation-heavy recursion no longer trips array allocation failed.

PiChudnovsky.sleela — binary-splitting Chudnovsky

1/pi = 12 Σ (−1)ᵏ (6k)! (13591409 + 545140134 k) / ((3k)! (k!)³ 640320^(3k+3/2))

evaluated exactly in integers by binary splitting — P/Q/T triples combined with only big ×, +, − (all riding the NTT multiply) — then scaled to digits places by pi = (426880 · √10005 · Q) / T, where the √ is one bigisqrt and the final scale is one bigdiv. Big integers are carried signed (sign + magnitude) in SLeeLa on top of the native ops. Verified digit-for-digit against an independent reference at 50, 1,000, and 10,000 digits.

Measured data — v3.0 (native big-integer kernel)

Whole-program wall time for each generator at a given digit count. One base-1e9 limb holds 9 decimal digits, so the working value is ≈ digits ÷ 9 limbs.

Decimal digitsLimbs (digits ÷ 9)Spigot (PiGenerator)Machin (PiMachin)Chudnovsky (PiChudnovsky)Notes
1,0001122 s<1 s1 sfixed setup dominates; all three near-equal
10,0001,11251 s3 s4 sChudnovsky after the R1 fast-isqrt seed (was 9 s)
50,0005,556— (hours)~5 min (est.)87 sspigot off-chart; was 194 s before R1

Kernel: native bigmul (NTT/Karatsuba) + bigadd + bigdivmod + the v3.0 additions bigsub / bigdiv / bigisqrt. Measured with the source-built compiler (impl/build/sleela) on this machine; each figure is a single timed run and varies a few percent run to run. Spigot and Machin are O(digits²); the 50,000-digit spigot run does not complete in a practical window (hours) and Machin's is an extrapolation from its 10,000-digit point. Chudnovsky outputs were checked digit-for-digit against an independent reference at 1,000 / 10,000 / 50,000. The Chudnovsky column now reflects the R1 fast-isqrt seed (see NATIVE.ADD.md): 10k 9 s → 4 s, 50k 194 s → 87 s (~2.2–2.5×). The binary-splitting recursion is quasi-linear (~0.5% of the run); bigisqrt is now ~85% because each of its few Newton iterations still calls the schoolbook O(n²) bigdiv. Making that divide quasi-linear (a correct Newton reciprocal, R2 — scaffolded but not yet converging) is what reaches the ~O(d·log²d) regime.

The graph — wall time vs digit count (the three generators)

Seconds (vertical) against decimal digits (horizontal), from the measured points above. The spigot's 50,000-digit point is off the top of the axis (hours), so it is capped at the chart edge; Machin's is its ~5-minute estimate. Chudnovsky is the lowest curve at every reachable size.

xychart-beta
    title "Pi generator wall time vs digits (lower is better)"
    x-axis "Decimal digits" [1000, 10000, 50000]
    y-axis "Wall time (seconds)" 0 --> 300
    line "spigot"     [2, 51, 300]
    line "machin"     [1, 3, 300]
    line "chudnovsky" [1, 4, 87]

Plain-text plot (same data)

 time (s)
 300 |                                   x spigot (50k: hours, off-axis)
     |                                   o machin (50k: ~5 min, off-axis)
 100 |
  87 |                                   * chudnovsky (50k: 87 s, after R1)
  50 |                 x spigot (10k: 51 s)
     |
   4 |                 * chudnovsky (10k, after R1)
   3 |  . *o           o machin (10k: 3 s)
   0 |  *o (1k: ~1 s all three)
     +------------------------------------------------------------
        1k              10k                           50k   digits

On a linear axis the spigot's quadratic blow-up is obvious while Chudnovsky stays near the floor; even Machin (also O(d²) but native-divide-driven) is an order of magnitude under the spigot. The three curves meet only at ~1,000 digits, where the fixed setup cost dominates the math.

Honest status of the exponent. The binary-splitting recursion is quasi-linear, but the single final division and √ still use a schoolbook O(n²) kernel, and that term now dominates (Chudnovsky 10k → 50k is ~21× for 5× digits ≈ exponent 1.9). So v3.0 is correct Chudnovsky with a quasi-linear core but an O(d²) tail. The remaining step — a Newton–Raphson reciprocal bigdiv and Newton bigisqrt that ride the NTT multiply — removes the tail and delivers the full ~O(d·log²d) regime (millions of digits in minutes). Everything it needs (fast bigmul, bigsub) is now in place; see NATIVE.ADD.md.

Max Rupplin — MEARVK LLC — 2026

Files 13