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

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);
}

CodePudding user response：

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);