/
computepi.html
73 lines (70 loc) · 2.19 KB
/
computepi.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
<html>
<head>
<title>Compute PI digits using BigInt</title>
</head>
<script>
const one = BigInt(1);
const two = BigInt(2);
const three = BigInt(3);
const four = BigInt(4);
const seven = BigInt(7);
const ten = BigInt(10);
// Based on "Unbounded Spigot Algorithms for the Digits of Pi" by Jeremy Gibbons
// https://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/spigot.pdf
// Namely a JS adaptation of the following Haskell code:
// > pi = g(1,0,1,1,3,3) where
// > g(q,r,t,k,n,l) = if 4*q+r-t<n*t
// > then n : g(10*q,10*(r-n*t),t,k,div(10*(3*q+r))t-10*n,l)
// > else g(q*k,(2*q+r)*l,t*l,k+1,div(q*(7*k+2)+r*l)(t*l),l+2)
class ComputePI {
constructor() {
this.q = BigInt(10);
this.r = BigInt(-30);
this.t = BigInt(3);
this.k = BigInt(2);
this.n = BigInt(0);
this.l = BigInt(5);
this.digitsYielded = 0;
}
yieldDigit() {
while (four * this.q + this.r - this.t >= this.n * this.t) {
this.t *= this.l;
this.n = (this.q * (seven * this.k + two) + this.r * this.l) / this.t;
this.r = (two * this.q + this.r) * this.l;
this.q *= this.k;
this.k += one;
this.l += two;
}
const n = this.n;
this.digitsYielded += 1;
this.q *= ten;
const r = ten * (this.r - n * this.t);
this.n = (three * this.q + ten * this.r) / this.t - ten * n;
this.r = r;
return n;
}
}
function configureSpigot() {
let spigot = new ComputePI();
const maxDigits = 1e4;
const maxDuration = 5;
let pi = "π=3.";
const computeDigits = function() {
const start = performance.now();
while (spigot.digitsYielded < maxDigits && performance.now() - start < maxDuration) {
pi += spigot.yieldDigit() + "­";
}
if (spigot.digitsYielded >= maxDigits) {
pi += "...";
}
document.body.innerHTML = pi;
if (spigot.digitsYielded < maxDigits) {
window.requestAnimationFrame(computeDigits);
}
};
computeDigits();
}
</script>
<BODY onload="configureSpigot()">
π=3.14... (to be overwritten by the script)</BODY>
</html>