1/*
2 * PI computation in Javascript using the BigInt type
3 */
4"use strict";
5
6/* return floor(log2(a)) for a > 0 and 0 for a = 0 */
7function floor_log2(a)
8{
9    var k_max, a1, k, i;
10    k_max = 0n;
11    while ((a >> (2n ** k_max)) != 0n) {
12        k_max++;
13    }
14    k = 0n;
15    a1 = a;
16    for(i = k_max - 1n; i >= 0n; i--) {
17        a1 = a >> (2n ** i);
18        if (a1 != 0n) {
19            a = a1;
20            k |= (1n << i);
21        }
22    }
23    return k;
24}
25
26/* return ceil(log2(a)) for a > 0 */
27function ceil_log2(a)
28{
29    return floor_log2(a - 1n) + 1n;
30}
31
32/* return floor(sqrt(a)) (not efficient but simple) */
33function int_sqrt(a)
34{
35    var l, u, s;
36    if (a == 0n)
37        return a;
38    l = ceil_log2(a);
39    u = 1n << ((l + 1n) / 2n);
40    /* u >= floor(sqrt(a)) */
41    for(;;) {
42        s = u;
43        u = ((a / s) + s) / 2n;
44        if (u >= s)
45            break;
46    }
47    return s;
48}
49
50/* return pi * 2**prec */
51function calc_pi(prec) {
52    const CHUD_A = 13591409n;
53    const CHUD_B = 545140134n;
54    const CHUD_C = 640320n;
55    const CHUD_C3 = 10939058860032000n; /* C^3/24 */
56    const CHUD_BITS_PER_TERM = 47.11041313821584202247; /* log2(C/12)*3 */
57
58    /* return [P, Q, G] */
59    function chud_bs(a, b, need_G) {
60        var c, P, Q, G, P1, Q1, G1, P2, Q2, G2;
61        if (a == (b - 1n)) {
62            G = (2n * b - 1n) * (6n * b - 1n) * (6n * b - 5n);
63            P = G * (CHUD_B * b + CHUD_A);
64            if (b & 1n)
65                P = -P;
66            Q = b * b * b * CHUD_C3;
67        } else {
68            c = (a + b) >> 1n;
69            [P1, Q1, G1] = chud_bs(a, c, true);
70            [P2, Q2, G2] = chud_bs(c, b, need_G);
71            P = P1 * Q2 + P2 * G1;
72            Q = Q1 * Q2;
73            if (need_G)
74                G = G1 * G2;
75            else
76                G = 0n;
77        }
78        return [P, Q, G];
79    }
80
81    var n, P, Q, G;
82    /* number of serie terms */
83    n = BigInt(Math.ceil(Number(prec) / CHUD_BITS_PER_TERM)) + 10n;
84    [P, Q, G] = chud_bs(0n, n, false);
85    Q = (CHUD_C / 12n) * (Q << prec) / (P + Q * CHUD_A);
86    G = int_sqrt(CHUD_C << (2n * prec));
87    return (Q * G) >> prec;
88}
89
90function main(args) {
91    var r, n_digits, n_bits, out;
92    if (args.length < 1) {
93        print("usage: pi n_digits");
94        return;
95    }
96    n_digits = args[0] | 0;
97
98    /* we add more bits to reduce the probability of bad rounding for
99      the last digits */
100    n_bits = BigInt(Math.ceil(n_digits * Math.log2(10))) + 32n;
101    r = calc_pi(n_bits);
102    r = ((10n ** BigInt(n_digits)) * r) >> n_bits;
103    out = r.toString();
104    print(out[0] + "." + out.slice(1));
105}
106
107var args;
108if (typeof scriptArgs != "undefined") {
109    args = scriptArgs;
110    args.shift();
111} else if (typeof arguments != "undefined") {
112    args = arguments;
113} else {
114    /* default: 1000 digits */
115    args=[1000];
116}
117
118main(args);
119