PiMachin.sleela
pi-generator/PiMachin.sleela · 308 line(s) · sleela
#sleela 2.9
<< PiMachin.sleela -- compute Pi with Machin's formula over the NATIVE
big-integer kernel, then stream the digits to a local file.
WHY THIS EXISTS. PiGenerator.sleela uses the Rabinowitz-Wagon spigot, which
is O(digits^2) in INTERPRETED SLeeLa bytecode: every one of `digits` passes
sweeps a `digits`-length int[] element by element, so millions of digits take
months of wall time (see pi-generator/README.md, "Performance - Version 2.0").
This program does the heavy arithmetic in the native C big-integer kernel
instead, reached through the VM opcodes bigmul (OP_BIGMUL, NTT/Karatsuba),
bigadd (OP_BIGADD) and bigdivmod (OP_BIGDIVMOD, divide by a SMALL integer).
The per-term cost is two native base-1e9 long-divisions over a `digits`-length
limb array -- C speed, not an interpreted per-element loop -- so the constant
factor is far smaller than the spigot even though the term count is similar.
ALGORITHM. Machin's formula:
pi = 16 * arctan(1/5) - 4 * arctan(1/239)
with the Maclaurin series arctan(1/x) = sum_{k>=0} (-1)^k / ((2k+1) x^(2k+1)).
Everything is kept as a scaled integer N ~= pi * 10^(digits+guard) stored as
a base-1,000,000,000 limb int[] (little-endian: limb 0 is least significant,
one limb holds 9 decimal digits). For each arctan we keep a running power
P_k = SCALE / x^(2k+1)
advanced by a single bigdivmod(P, x*x, P) per step (x*x = 25 and 57121 are
both < 1e9, so one native divide), then the term T_k = P_k / (2k+1) is
another single native divide ((2k+1) <= ~10^7 even at 7,000,000 digits, so it
stays a SMALL divisor). Even-k terms are added to a positive accumulator and
odd-k terms to a negative one; the two are combined with a limb-wise subtract.
WHY NOT CHUDNOVSKY. Classic Chudnovsky needs big-by-big division and a big
square root (of 10005). The VM exposes only bigmul, bigadd and bigdivmod
(small divisor) -- there is no native big/big divide or big sqrt -- so a
Machin arctan series, whose every division is by a small integer, is the
fastest formula expressible on today's kernel. The only non-native helper is
a limb-wise subtract (bigsub below), which is O(digits) and runs a handful of
times, so it does not affect the asymptotics.
OUTPUT. Digits are formatted straight from the final limb array and streamed
to the file in fixed-size chunks, so memory stays flat. >>
class PiMachin {
<< Decimal digits of Pi to compute after the leading "3.". Default 10,000:
it finishes in well under a second here and matches the reference
exactly. Raise it freely -- the native kernel scales far better than the
spigot (see README Performance - Version 2.0). >>
int DIGITS = 10000;
<< Guard digits carried internally and dropped at the end, so the last few
printed digits are not polluted by truncation of the series tail. >>
int GUARD = 16;
< Output file, digit-count stamped. >
String OUT_PATH = "pi-machin.txt";
< Digits to buffer before each write() (keeps memory flat). >
int CHUNK = 4096;
< One base-1e9 limb holds 9 decimal digits. >
int DIGITS_PER_LIMB = 9;
int BASE = 1000000000;
< Streaming state. >
int fd = -1;
String buf = "";
int bufLen = 0;
int emitted = 0;
<< --- limb helpers ------------------------------------------------------
All numbers are non-negative base-1e9 int[] arrays, little-endian. We
keep a fixed working width (nlimbs) so every operand lines up. >>
int nlimbs = 0;
< Allocate a zeroed limb array of the working width. >
int[] newBig() {
int[] a = new int[nlimbs];
int i = 0;
while (i < nlimbs) { a[i] = 0; i = i + 1; }
return a;
}
< Copy src into a fresh working-width array. >
int[] copyBig(int[] src) {
int[] a = new int[nlimbs];
int i = 0;
while (i < nlimbs) { a[i] = src[i]; i = i + 1; }
return a;
}
<< Copy the low nlimbs limbs of a WIDER source (e.g. an nlimbs+1 bigadd
result) into a fresh working-width array, dropping the top carry limb
(which is zero by construction for our SCALE-bounded partial sums). >>
int[] copyBigN(int[] src) {
int[] a = new int[nlimbs];
int i = 0;
while (i < nlimbs) { a[i] = src[i]; i = i + 1; }
return a;
}
< Set a limb array to a small non-negative integer value (< BASE). >
void setSmall(int[] a, int v) {
int i = 0;
while (i < nlimbs) { a[i] = 0; i = i + 1; }
a[0] = v;
}
<< Is `a` all zeros? Used to stop a series once the running term underflows
to 0 at the working precision (no point adding zero terms). >>
boolean isZero(int[] a) {
int i = 0;
while (i < nlimbs) { if (a[i] != 0) { return false; } i = i + 1; }
return true;
}
<< Limb-wise subtract: a = a - b, assuming a >= b (true by construction here,
since the positive partial sum of an alternating, strictly-decreasing
arctan series always dominates the negative one). O(nlimbs). >>
void subFrom(int[] a, int[] b) {
int borrow = 0;
int i = 0;
while (i < nlimbs) {
int d = a[i] - b[i] - borrow;
if (d < 0) { d = d + BASE; borrow = 1; } else { borrow = 0; }
a[i] = d;
i = i + 1;
}
}
<< --- Machin core -------------------------------------------------------
Accumulate SCALE * arctan(1/x) into `acc` (positive terms) minus `neg`
(odd terms), using one running power P advanced by /x^2 each step and one
/(2k+1) per term. `scale` is passed in as the limb array 10^(working
digits). Returns via the two accumulator arrays (acc already holds the
result after the final subFrom). >>
void arctanInto(int[] acc, int x, int[] scale) {
<< x^2 is 25 or 57121 here, both < BASE, so dividing by it is one native
bigdivmod per step. The hot loop is COPY-FREE: every big op writes in
place (the native kernel snapshots its inputs into its own buffers
first, so aliasing input == result is safe), and the double-buffered
accumulators swap by REFERENCE (O(1)) instead of copying O(nlimbs)
limbs each term. That removes the per-term O(nlimbs) interpreted copy
that would otherwise make this O(digits^2) in the interpreter. >>
int xx = x * x;
<< pos accumulates even-k terms, neg the odd-k. The running `power` is
divided IN PLACE each step (the native kernel snapshots its input
before writing, so result==input aliasing is safe) -- no copy there.
bigadd, however, strictly requires its result array to be
max(len(a),len(b))+1 limbs, so it cannot write back into an operand of
the same width; the accumulate step therefore adds into a wider `sum`
buffer and copies the low nlimbs back. That single O(nlimbs) copy per
term is the dominant interpreted cost and keeps the whole series
O(digits^2) -- faster than the spigot by a large constant (the heavy
divides are native), but the same complexity class. True sub-quadratic
Pi needs a native big/big divide or binary splitting, which this VM
kernel does not expose yet (see README). >>
int[] pos = newBig();
int[] neg = newBig();
<< power starts at SCALE/x; divided by x^2 in place each step. >>
int[] power = copyBig(scale);
int remQ = bigdivmod(power, x, power);
int[] term = newBig();
int[] sum = new int[nlimbs + 1];
int zi = 0;
while (zi < nlimbs + 1) { sum[zi] = 0; zi = zi + 1; }
int k = 0;
boolean running = true;
while (running) {
<< denom = 2k+1 stays <= ~10^7 even at 7,000,000 digits, a valid
SMALL bigdivmod divisor. term = power / (2k+1). >>
int denom = 2 * k + 1;
int r1 = bigdivmod(power, denom, term);
if (isZero(term)) { running = false; }
else {
if ((k % 2) == 0) {
int s = bigadd(pos, term, sum);
pos = copyBigN(sum);
} else {
int s = bigadd(neg, term, sum);
neg = copyBigN(sum);
}
int r2 = bigdivmod(power, xx, power);
k = k + 1;
}
}
<< acc = pos - neg. >>
int i = 0;
while (i < nlimbs) { acc[i] = pos[i]; i = i + 1; }
subFrom(acc, neg);
}
<< Multiply a limb array by a small integer (< BASE) in place-ish, returning
a fresh array. Implemented via bigmul against a one-limb multiplier so we
reuse the native kernel. >>
int[] mulSmall(int[] a, int m) {
int[] mm = new int[1];
mm[0] = m;
int[] r = new int[nlimbs + 1];
int i = 0;
while (i < nlimbs + 1) { r[i] = 0; i = i + 1; }
int sig = bigmul(a, mm, r);
< fold back into working width (product fits: m is tiny, we carry guard) >
int[] out = newBig();
i = 0;
while (i < nlimbs) { out[i] = r[i]; i = i + 1; }
return out;
}
void main() {
int digits = DIGITS;
<< work is the internal decimal precision: the requested digits plus a
few guard digits dropped at the end. >>
int work = digits + GUARD;
nlimbs = (work + DIGITS_PER_LIMB) / DIGITS_PER_LIMB + 2;
<< SCALE = 10^(working-limb-digits). Build it as a limb array: the top
limb pattern that represents 10^(9 * (nlimbs-k)). Simplest correct
form: start from 1 and multiply by 10, `9*(nlimbs-2)`-ish times. To
stay O(nlimbs) we instead set the limb that lands on a 9-boundary. >>
int[] scale = newBig();
<< Place 1 at the most-significant guard limb so SCALE = BASE^(nlimbs-1),
i.e. 10^(9*(nlimbs-1)) -- an exact power of ten on a limb boundary,
which keeps every /x and /(2k+1) a clean base-1e9 long division. >>
scale[nlimbs - 1] = 1;
< A = SCALE * arctan(1/5) ; B = SCALE * arctan(1/239) >
int[] a5 = newBig();
arctanInto(a5, 5, scale);
int[] a239 = newBig();
arctanInto(a239, 239, scale);
< pi*SCALE = 16*A - 4*B. 16 and 4 are small; build both then subtract. >
int[] left = mulSmall(a5, 16);
int[] right = mulSmall(a239, 4);
int[] pi = copyBig(left);
subFrom(pi, right);
<< Emit. pi is 3.14159... * BASE^(nlimbs-1). The integer part (3) lives
in the top limb; the fractional limbs follow in descending order, each
printed as 9 zero-padded decimal digits. We print "3." then stream
`digits` fractional digits. >>
fd = openFile(OUT_PATH, "w");
if (fd < 0) { print("PiMachin: could not open " + OUT_PATH); return; }
<< Top limb is the integer part (should be 3). Write "3." . >>
put1(pi[nlimbs - 1]);
buf = buf + ".";
bufLen = bufLen + 1;
<< Fractional limbs: from nlimbs-2 down to 0, each limb is exactly 9
decimal digits (zero-padded), emitted most-significant digit first,
until the DIGITS budget is met. >>
int li = nlimbs - 2;
int produced = 0;
while (li >= 0 && produced < digits) {
produced = emitLimb(pi[li], digits, produced);
li = li - 1;
}
flush();
close(fd);
print("PiMachin: wrote Pi to " + OUT_PATH
+ " (" + produced + " fractional digits, target " + digits + ")");
}
<< Emit a single small non-negative integer (the integer part, 0..9 here)
with no padding. >>
void put1(int v) {
buf = buf + v;
bufLen = bufLen + 1;
emitted = emitted + 1;
if (bufLen >= CHUNK) { flush(); }
}
<< Emit one base-1e9 limb as exactly 9 zero-padded decimal digits, most
significant first, stopping at the overall `digits` budget. Digits are
extracted arithmetically (no string indexing, which SLeeLa lacks): walk
powers of ten from 10^8 down to 10^0, printing (limb / p) % 10 each step.
Returns the updated produced count. >>
int emitLimb(int limb, int digits, int produced) {
<< p starts at 10^8, the most-significant of a limb's 9 digits. >>
int p = 100000000;
while (p >= 1 && produced < digits) {
int d = (limb / p) % 10;
buf = buf + d;
bufLen = bufLen + 1;
produced = produced + 1;
emitted = emitted + 1;
if (bufLen >= CHUNK) { flush(); }
p = p / 10;
}
return produced;
}
< Write the buffered chunk to the file and reset the buffer. >
void flush() {
if (bufLen > 0) {
write(fd, buf);
buf = "";
bufLen = 0;
}
}
}