Three efficient JavaScript functions that converge to pi extremely fast

Question

I am learning JavaScript and decided to translate my Python scripts into JavaScript.

Approximations of π are extremely popular programming challenges and I am sure they must be a staple of the challenges one must overcome to learn a programming language.

I am sure you must be bored of this kind of questions but I have tested many algorithms and selected the algorithms that converge the fastest:

> console.log(pi(50))
3.1415926535897922
undefined
> console.log(BBP(11))
3.141592653589793
undefined
> console.log(Ramanujan(3))
3.141592653589793
undefined
>

The first function takes 50 iterations to generate the closest value before precision loss, the second function takes only 11 iterations to get the closest approximation of π possible within the IEEE-754 Binary64 (double) format, whereas the last function only takes THREE iterations!

---

Code

function pi (t) {
    function db (x) {
        if (x <= 0) { return 1 }
        return x * db(x - 2)
    }
    let term = (x) => db(2 * x) / db(2 * x + 1) * 0.5 ** x
    const stack = []
    for (let i=0; i<t; i++) { stack.push(term(i)) }
    return 2 * stack.reduce((s, n) => s + n, 0)
}

function BBP (t) {
    const stack = []
    for (let k=0; k<t; k++) {
        let a = 1/16**k
        let b = 4/(8*k+1)
        let c = 2/(8*k+4)
        let d = 1/(8*k+5)
        let e = 1/(8*k+6)
        let item = a * (b - c - d - e)
        stack.push(item)
    }
    return stack.reduce((s, n) => s + n, 0)
}

function Ramanujan (t) {
    function factorial (n) {
        var f = 1
        for (let i=1; i<=n; i++) { f *= i }
        return f
    }
    let term = (k) => (factorial(4*k) * (1103 + 26390*k)) / (factorial(k)**4 * 396**(4*k))
    const stack = []
    for (let i=0; i<t; i++) { stack.push(term(i)) }
    var sum = stack.reduce((a, b) => a + b, 0)
    return 1 / (2 * 2**.5 * sum/9801)
}

console.log(pi(50))
console.log(BBP(11))
console.log(Ramanujan(3))

How can they be improved? (I wrote them all within half an hour.)

Answer 1

In terms of more precision, I can't really help there... But, in terms of general code styling and performance, I'd be happy to give some pointers. This is good code, but slightly inconsistent (which is understandable, since you're new to JS!).

I'm going to mainly focus on the Ramanujan function, but the advice can be applied in other areas too.

Styling

You seem to keep switching between var, let and const and using them in inappropriate contexts. var is the older syntax, and let and const are both newer. There are some differences to let and var under the hood, mainly surrounding scoping: let is block scoped, var is function scoped. const is used to annotate immutable variables, but they're not truly immutable all the time... Another weird remnant of poor language design choices. You can use Object.freeze() to get (more)true immutability.

I'd stick to using let as it's the way that variables should have been designed in the first place. A good article explaining the pitfalls of var: https://hackernoon.com/why-you-shouldnt-use-var-anymore-f109a58b9b70

Next, const. You originally assigned an empty array as a const, then pushed values to it. Whilst this is technically allowed in JS, it's not great practice. A constant should remain immutable.

Alongside that, you also used the arrow function syntax and stored it's name using the let keyword... Which implies that it may be mutable in the future, which of course is not the case :)

Performance

The runtime of this algorithm is fast, but there's 3 things that I picked up on that will improve it's performance.

Firstly, when you calculate the terms, you push each of them into an array. Once the loop finishes, you iterate over that array and then add each of them together (in the reduce function). Whilst this works, it's sub-optimal, as you have to run 2 loops, when you can do it all in the first loop by simply adding each result to a running total.

Secondly, the return function calculates: 2 * 2 ** 0.5 before returning... This is a bit of a waste, as the values are not dynamic- and so the result of that calculation could be inserted as a constant, so that those operations are not wasted at run time.

Finally, and this one's extremely pedantic (and slightly mystical), when raising k to the power n, I've found that k ** n is slightly slower than Math.pow(k, n). This one might not even count as advice to be honest, as the speed gain is absolutely minimal.

Refactored

function Ramanujan2(t) {
    function factorial(n) {
        let f = 1;
        for (let i=1; i<=n; i++) {
            f *= i;
        }
        return f;
    }

    // In my experience, Math.pow seems to be faster than **
    const term = k => (factorial(4*k) * (1103 + 26390*k)) / (Math.pow(factorial(k), 4) * Math.pow(396, 4*k));

    // Rather than allocate each term to an array, then iterate that array and
    // add each number; simply add the numbers to a total as they're calculated.
    // More efficient on memory, and slightly faster as only one iteration of the
    // set is required.
    let sum = 0;
    for (let i=0; i<t; i++) {
        sum += term(i);
    }

    // Factored out two operations ( * and a ** ) into a constant representing
    // the actual value calculated... so it's a fixed value every time.
    return 1 / ( 2.8284271247461903 * sum/9801 );
}

Finally, if you ever need to get the value of Pi outside of this learning exercise, you can use the Math.PI constant provided by default.