Javascript - How do I make this pi calculating algorithm run faster?

Question

How this algorithm works: It first generates random coordinates for a point. It then finds the distance of each point from the middle of the circle. If the distance <= 1, then the point is in the circle, otherwise outside the circle. The ratio between the number of points in the circle and the number of total points is close to pi.

I want to make this algorithm run faster. How do I do it?

function calc(iterations) {
    pointCircle = 0, total = 0, x = 0, y = 0, distance = 0, pi = 0;
    for (let i = 0; i < iterations; i++) {
        x = Math.random().toFixed(1);
        y = Math.random().toFixed(1);
        distance = Math.sqrt(x * x + y * y);
        if (distance <= 1) {pointCircle++;}total++;
    }
    pi = 4 * (pointCircle / total); console.log(pi);
}

why `sqrt`? you know `sqrt(x*x + y*y) <= sqrt(1)` is the same as `x*x + y*y <= 1` why fixed ? you can leave the floats in the conversion to int as fixed point might be slower ... also this algo converge very slowly so its better to use it continuously in some thread and output the iterated pi value every 250 or more [ms] ... and stop once you saturate precision or on some button ... also save/load state on app end/start is a good idea to continue where you left also see "duplicate" [Optimize estimating Pi function C++](https://stackoverflow.com/a/70142282/2521214) — Spektre, Sep 05 '22 at 06:35

CertainPerformance · Accepted Answer · 2022-09-05T03:36:37.320

The .toFixed(1) is making the calculation a lot more inaccurate and is consuming a lot of CPU time, at least on V8. Remove that, and the time required for a given number of (large) iterations appears to drop by a factor of around 8.

// Original code
function calc(iterations) {
    pointCircle = 0, total = 0, x = 0, y = 0, distance = 0, pi = 0;
    for (let i = 0; i < iterations; i++) {
        x = Math.random().toFixed(1);
        y = Math.random().toFixed(1);
        distance = Math.sqrt(x * x + y * y);
        if (distance <= 1) {pointCircle++;}total++;
    }
    pi = 4 * (pointCircle / total); console.log('pi', pi);
}
setTimeout(() => {
  const t0 = performance.now();
  calc(1000000)
  console.log('time', performance.now() - t0);
}, 2000);

// Modified code
function calc(iterations) {
    pointCircle = 0, total = 0, x = 0, y = 0, distance = 0, pi = 0;
    for (let i = 0; i < iterations; i++) {
        x = Math.random();
        y = Math.random();
        distance = Math.sqrt(x * x + y * y);
        if (distance <= 1) {pointCircle++;}total++;
    }
    pi = 4 * (pointCircle / total); console.log('pi', pi);
}
setTimeout(() => {
  const t0 = performance.now();
  calc(1000000)
  console.log('time', performance.now() - t0);
}, 2000);

Another improvement can be had by properly scoping your variables, instead of reassigning properties on the window object, which looks to further improve the speed by around 3x on V8.

// Modified code 2
function calc(iterations) {
    let total = 0;
    let pointCircle = 0;
    for (let i = 0; i < iterations; i++) {
        const x = Math.random();
        const y = Math.random();
        if (Math.sqrt(x * x + y * y) <= 1) { pointCircle++; }
        total++;
    }
    const pi = 4 * (pointCircle / total); console.log('pi', pi);
}
setTimeout(() => {
  const t0 = performance.now();
  calc(1000000)
  console.log('time', performance.now() - t0);
}, 2000);

Thanks btilly, the Math.sqrt isn't needed either.

After all the sqrt is less than 1 if and only if the original number is.

which shaves off a bit.

// Modified code 2
function calc(iterations) {
    let total = 0;
    let pointCircle = 0;
    for (let i = 0; i < iterations; i++) {
        const x = Math.random();
        const y = Math.random();
        if (x * x + y * y <= 1) { pointCircle++; }
        total++;
    }
    const pi = 4 * (pointCircle / total); console.log('pi', pi);
}
setTimeout(() => {
  const t0 = performance.now();
  calc(1000000)
  console.log('time', performance.now() - t0);
}, 2000);

You should be able to speed it up again by dropping the `Match.sqrt`. After all the `sqrt` is less than 1 if and only if the original number is. — btilly, Sep 05 '22 at 03:34

Javascript - How do I make this pi calculating algorithm run faster?

1 Answers1