Home /Modules/pi-generator/BIGMUL-DISTRIBUTION.md

BIGMUL-DISTRIBUTION.md

pi-generator/BIGMUL-DISTRIBUTION.md · 233 line(s) · markdown

Big-integer multiply — distribution over digit scale

A linear distribution graph of the native big-integer multiply (OP_BIGMUL) cost as the operand size grows, measured on this calculus. The requested basis points are 0, 1,000, 100,000, and 10,000,000 decimal digits; two extra points (10,000 digits, and the practical ceiling) are added so the shape of the curve is visible.

All times are the native bigmul() path (the C big-integer kernel reached through opcode OP_BIGMUL), timed in SLeeLa with timeMonotonicNanos() on bigmul(a, b, result) over base-1,000,000,000 limb int[] arrays. One decimal digit ≈ 1/9 of a limb (a limb holds 9 digits).

Two models are documented below. The original figures (v1.0) were taken on the earlier VM generation, whose multiply kernel was schoolbook + Karatsuba and whose single-array cap was SL_MAX_ARRAY_LEN = 1,048,576 (2²⁰). The newer figures (v2.0) were taken on the current runtime (SLeeLa™ Language/Runtime 1.3.2-pro), whose kernel adds an NTT (number-theoretic transform) path for large products and whose array cap was raised to SL_MAX_ARRAY_LEN = 16,777,216 (2²⁴). The headline consequence: the 10,000,000-digit multiply is now reachable as a single bigmul() call, which it was not on v1.0.

Measured data — v1.0 (earlier VM generation)

Decimal digitsLimbs (digits ÷ 9)Native multiply timeNotes
000 µsdegenerate baseline (empty operand)
1,00011221 µs
10,0001,112699 µs
100,00011,11224,517 µs (≈ 24.5 ms)
10,000,0001,111,112— (not a single multiply)exceeded the VM array cap; see below

Kernel: schoolbook + Karatsuba (O(n^1.585)), single-array cap 2²⁰. Measured with the source-built compiler (impl/build/sleela), operands filled with repeating limbs 123456789 × 987654321. Times vary a few percent run to run.

Measured data — v2.0 (current runtime, NTT kernel)

Decimal digitsLimbs (digits ÷ 9)Native multiply timeNotes
000 µsdegenerate baseline (empty operand)
1,00011229 µsKaratsuba path (below the NTT threshold)
10,0001,1129,600 µs (≈ 9.6 ms)NTT path
100,00011,112200,000 µs (≈ 200 ms)NTT path
1,000,000111,1121,900,000 µs (≈ 1.9 s)NTT path
10,000,0001,111,11217,900,000 µs (≈ 17.9 s)now a single bigmul() call

Kernel: schoolbook + Karatsuba + NTT, single-array cap 2²⁴. Measured with the current prebuilt toolchain (working-binaries/sleela, SLeeLa™ Language/Runtime 1.3.2-pro), same operand fill as v1.0. Each figure is the median of three runs; times vary a few percent run to run. The NTT path (sl_bigmul_ntt) engages at SL_NTT_THRESHOLD = 512 limbs (≈ 4,600 digits), so every point from 10,000 digits up is on the NTT path; the 1,000-digit point (112 limbs) is still Karatsuba.

Measured data — v3.0 (native kernel, source-built, cap 2²⁵)

Decimal digitsLimbs (digits ÷ 9)Native multiply timeNotes
000 µsdegenerate baseline (empty operand)
1,00011223 µsKaratsuba path (below the NTT threshold)
10,0001,1121,593 µs (≈ 1.6 ms)NTT path
100,00011,11233,102 µs (≈ 33.1 ms)NTT path
1,000,000111,112321,422 µs (≈ 0.32 s)NTT path
10,000,0001,111,1123,160,647 µs (≈ 3.16 s)single bigmul() call; cap now 2²⁵

Kernel: schoolbook + Karatsuba + NTT (the OP_BIGMUL kernel is unchanged from v2.0), single-array cap raised to SL_MAX_ARRAY_LEN = 33,554,432 (2²⁵). OP_BIGMUL now also has the sibling ops bigsub / bigdiv / bigisqrt alongside it. Measured with the source-built compiler (impl/build/sleela) on this machine, same operand fill (123456789 × 987654321) as v1.0/v2.0; each figure is a single timed run and varies a few percent run to run. The large-operand points are markedly faster here than the v2.0 column (e.g. 10,000,000 digits ≈ 3.16 s vs 17.9 s): v2.0 was measured on the prebuilt working-binaries/sleela, so the gap is the host/build and run-to-run variance, not a kernel change — the asymptotic O(n log n) NTT shape is the same.

Reading the two tables together

The graph (linear axes)

Time (ms) on the vertical axis, decimal digits on the horizontal axis. Both models are plotted on the shared reachable range (0 … 100,000 digits) so the two curves can be compared directly. The 1,000,000- and 10,000,000-digit v2.0 points are far off the top of this scale (1.9 s and 17.9 s) and are summarised in the table above rather than squeezed onto this axis.

xychart-beta
    title "Native OP_BIGMUL cost vs operand size (linear) — v1.0 vs v2.0"
    x-axis "Decimal digits" [0, 1000, 10000, 100000]
    y-axis "Time (milliseconds)" 0 --> 200
    line [0, 0.021, 0.699, 24.517]
    line [0, 0.029, 9.6, 200]

Lower line = v1.0 (schoolbook + Karatsuba). Upper line = v2.0 (NTT kernel) on the same reachable range.

Plain-text plot (v2.0, reachable single-call range)

 time (ms)
200 |                                              * 100,000d (200 ms)
    |
150 |
    |
100 |
    |
 50 |
    |
 10 |                            * 10,000d (9.6)
  0 |  * 0d      * 1,000d (0.029)
    +----------------------------------------------------------------
       0        1k                 10k                 100k   digits
            ( 1,000,000d = 1.9 s and 10,000,000d = 17.9 s are off-chart )

The growth is superlinear, not linear

On both models the cost is not linear in the digit count. For v1.0, going from 1,000 → 100,000 digits is 100× the operands but about 1,167× the time (21 µs → 24,517 µs) — close to an n^1.5-style curve, which is what a Karatsuba multiply (O(n^1.585)) plus per-call array handling produces.

ModelStepDigit factorTime factorImplied exponent (log ratio)
v1.01,000 → 10,00010×33.3×≈ 1.52
v1.010,000 → 100,00010×35.1×≈ 1.55
v2.010,000 → 100,00010×20.8×≈ 1.32
v2.0100,000 → 1,000,00010×9.5×≈ 0.98
v2.01,000,000 → 10,000,00010×9.4×≈ 0.97

The v2.0 exponent falls toward ~1 as the operands grow, which is the O(n log n) NTT signature asserting itself: once the transform dominates, each 10× in digits costs only ~9.5× in time, not the ~35× that Karatsuba charged. So "linear distribution" is the requested framing, and v2.0's large-operand behaviour is the closest this kernel gets to it — a near-linear curve at scale, documented here rather than forced onto a straight line.

The 10,000,000-digit point

A single 10,000,000-digit multiply needs operands of ~1,111,112 limbs each.

This was a VM array/allocation ceiling, not a limit of the OP_BIGMUL kernel itself — the kernel is correct and fast at every size it can be handed (see lib/math/examples/BigMulVerify.sleela, which checks it against a pure-SLeeLa schoolbook multiply from ~370 to ~20,000 digits). Raising the cap and adding the NTT path is exactly what turned the 10,000,000-digit basis point from "off the chart" into a measured value.

How to reproduce

#sleela 2.5
material;
class Bench {
  long timeOne(int n) {
    int[] a = new int[n];
    int[] b = new int[n];
    int i = 0;
    while (i < n) { a[i] = 123456789; b[i] = 987654321; i = i + 1; }
    int[] r = new int[n + n];
    long t0 = timeMonotonicNanos();
    int sig = bigmul(a, b, r);
    long t1 = timeMonotonicNanos();
    return (t1 - t0) / 1000;      // microseconds
  }
  void main() {
    print("1000 digits:     " + timeOne(112)     + " us");
    print("10000 digits:    " + timeOne(1112)    + " us");
    print("100000 digits:   " + timeOne(11112)   + " us");
    print("1000000 digits:  " + timeOne(111112)  + " us");   // v2.0 cap permits this
    print("10000000 digits: " + timeOne(1111112) + " us");   // v2.0 single-call point
  }
}

Run with the current prebuilt toolchain (v2.0 figures above): working-binaries/sleela run <file>.sleela (with SLEELA_HOME/SLEELA_LIB set to the repo root and repo/lib). The v1.0 figures were taken the same way with the earlier source-built compiler; the top two print lines (1,000,000 and 10,000,000 digits) only complete on v2.0.

Version 3.0 — kernel siblings and a higher cap

The multiply figures above are unchanged in v3.0 (the OP_BIGMUL kernel is the same NTT/Karatsuba code). What changed around it:

The whole-program Pi runtime graph (spigot vs Machin vs Chudnovsky, which is where OP_BIGMUL pays off end to end) lives in README.md under "Performance — Version 3.0", since it measures generators rather than a single multiply.

MEARVK LLC — SLeeLa — 2026