Approximating PI

In this coding challenge we are going to try to approximate the value of PI using random number generation, Geometry and Cartesian Coordinates.

We will begin with an explainer of what the goal and solution path will be and from there we will visualise the output using p5.js.

The challenge

Given a random set of points on a 2D plane, estimate the value of PI.

This is not such an easy challenge to wrap your head around at first because how can you even begin to approximate PI with nothing more than some randomly generated points and a 2D plane? On the face of it, that would be like saying "Go to the shop and buy some milk and then use it to fly to the moon".

Nevertheless this challenge is what we will be tackling today by breaking it down and piecing a solution back together. As usual we will begin the implementation with some tests.

Tests

For the tests I will be using the Jest testing framework. If you have never used Jest before then I highly recommend you check it out. With that said, our tests are written as follows:

expect.extend({
  toBeWithinRange(received, floor, ceiling) {
    return {
      message: () =>
        `expected ${received} to be within range ${floor} - ${ceiling}`,
      pass: received >= floor && received <= ceiling,
    };
  },
  toBeEither(received, ...options) {
    return {
      message: () =>
          `expected ${received} to be one of ${options}`,
      pass: [...options].filter(current => {
        return Object.is(received, current);
      }).length === 1
    }
  }
});

describe("GuessPI", () => {
  it('Handles the four or zero case', () => {
    const answer = guessPI(1);
    expect(answer).toBeEither(0, 4);
  });

  it('puts PI within roughly 0.5 of the target', () => {
    const answer = guessPI(100);
    expect(answer).toBeWithinRange(Math.PI - 0.5, Math.PI + 0.5);
  });

  it('puts PI within roughly 0.3 of the target', () => {
    const answer = guessPI(1000);
    expect(answer).toBeWithinRange(Math.PI - 0.3, Math.PI + 0.3);
  });

  it('puts PI within 0.2 of the target', () => {
    const answer = guessPI(10000);
    expect(answer).toBeWithinRange(Math.PI - 0.2, Math.PI + 0.2);
  });

  it('puts PI within 0.14 of the target', () => {
    const answer = guessPI(100000);
    expect(answer).toBeWithinRange(Math.PI - 0.14, Math.PI + 0.14);
  });
});

Firstly we extend the default expect object with 2 helper functions:

1. One to check that the value we are looking for is within a range (inclusive)
2. One to check that the value we are looking for is one of two options

Next we test our implementation itself.

The first test checks if the guessPI function will return a 0 or a 4 when only 1 point is placed on the plane, this will become clearer as to why these values will be the only 2 epected values to return in such a case later when we implement the guessPI function. The second test gets us within 0.5 of PI, the third within 0.3, the fourth puts us within 0.2 and the last within 0.14.

Ok but how does it work?

Implementation

function guessPI(number) {
  let in_circle_count = 0;
  const in_square_count = number;

  for (let i = number; i > 0; i--) {
    const x = (Math.random() * 101) / 100;
    const y = (Math.random() * 101) / 100;
    const distance = x ** 2 + y ** 2;
    if (distance <= 1) in_circle_count++;
  }

  return 4 * (in_circle_count / in_square_count);
}

Upon reading this implementation you may be having an aha moment regarding how this actually works but for those of you who don't, let's break the implementation down.

The challenge was to approximate PI using only a 2D plane and a set of random points. Assuming that this plane is a square, approximating PI is actually relatively simple since a circle would fit nicely into a square, assuming the squares sides were the same length as the diameter of the circle. In other words, each side of the square in such a case would be twice the radius of the circle in length. All said, we can now use some high school maths to begin working out the value of PI.

Area of the circle:

Area of the square:

The amount of the square taken up by the circle:

Since the $r^{2}$ values cancel each other out we can simplify the ratio calculation down to just being:

From this we can work out PI to be:

Now we know how we can approximate the value of PI, it's just the calculation of the amount of points within the circle comparitive to those within the square multiplied by 4!

Visualising our implementation

For the following visualisation I have used the p5.js library and adapted the code somewhat from our implementation so as to draw the points.

For this visualisation I wanted to simplify things further and only use a positive cartesian coordinate system and thus we only use a quarter circle section to calculate upon within the square.

This works exactly the same as the full circle in a square calculation since we are just scaling things down 1 to 1 in terms of the square and circle.

Feel free to read the comments in the code to further understand how things are working and otherwise just press the "play" button or click the "open in new tab" button to see the vizualisation in action!

Conclusions

Considering the outline of the challenge we have actually managed to figure out how we can approximate the mathematical constant PI with only a 2D plane and some random points on that plane.

I hope that you found some value in todays post and if you have any questions, comments or suggestions, feel free to leave those in the comments area below the post!