JavaScriptCoding challenges

Calculating π inside an infinite-length List class

CategoryAlgorithms
Published20 January, 2023
Last updated21 January, 2023
AuthorKelly

I recently faced a coding challenge where the result had to be a List class that could handle infinite-length lists. As part of the solution, the List class had to have a PI() method that should return a calculation of π. Long story short, I decided to handle infinity with generator functions and used this same concept to implement the PI() method generator.

Here is an overview of the involved methods to calculate π:

class List { constructor(generator, min = 0, max = Infinity) { /* ... */} // Implementation of other list methods... get(n) { /* Obtains a value based on the number provided */ } static arctan(x) { /* Generator for Arctan series */ } static get PI() { /* Generator for PI calculation */ } }

This is an overview of how the implementation was built, we can appreciate:

  1. The constructor method is the one receiving the generator function and storing it for later use.
  2. The arctan method receives a parameter named x that we will get in detail later on.
  3. The PI method is of type get, which means we can directly invoke it and reference its values based on the generator function.

Moving forward, we are going to quickly analyze a few steps before the construction of the arctan(x) method.

Arctan (trigonometry)

The formula I used to build the arctan(x) method refers to this concept of inverse trigonometry functions being arctan one of the most important ones. Since arctan has many different uses, I had to focus only on those used for calculating π. For now, keep in mind the following formula:

const PI = 4 * ( arctan(1/2) + arctan(1/3) );

This is a Machin-like formula to calculate the approximate value of π, more specifically it is Euler's solution that implements the Taylor series, a representation of the following infinite sum:

Arctan function with Taylor series

Or if we translate it to code:

0 + x^1/1 - x^3/3 + x^5/5 - x^7/7 + ...Continues infinitely

So, here is the implementation of the arctan(x) method I ended up with:

static arctan(x) { function* generator() { let sum = 0; for(let i = 0; true; i++) { sum += (Math.pow(-1, i) * Math.pow(x, 2 * i + 1)) / (2 * i); yield sum; } } return new List(generator); }

For a better understanding, I will explain the formula in two parts:

  1. Controlling the current sign.
  2. Implementation of the Taylor series formula.

Controlling the current sign

Since I decided to have a variable that works as a counter (i) I was able to determine the current operation sign between + and - with the following code:

Math.pow(-1, i) // Examples console.log(Math.pow(-1, 0)); // 1 console.log(Math.pow(-1, 1)); // -1 console.log(Math.pow(-1, 2)); // 1 console.log(Math.pow(-1, 3)); // -1

And since the formula uses the inline sum operator += it automatically determines the sign that should be used in the current iteration.

Implementation of the Taylor series formula

The representation of the x^1/1 in code is the following fragment of code:

Math.pow(x, 2 * i + 1) / (2 * i);

And since it is a sum of all those elements, the result is always being saved to the sum variable:

sum += (Math.pow(-1, i) * Math.pow(x, 2 * i + 1)) / (2 * i);

Implementing PI() method

With the previous formula already working, implementing the PI() method was simpler because, as mentioned previously, I used Euler's solution to calculate π. (The formula I suggested to keep in mind)

static get PI() { function* generator() { let counter = 0; let pi = 0; yield pi; // This formula: const [ arc1_2, arc1_3 ] = [ List.arctan(1 / 2), List.arctan(1 / 3) ]; while(true) { // PI = 4 * ( arctan(1/2) + arctan(1/3) ) // Getting the length based on current iteration of PI pi = 4 * (arc1_2.get(counter) + arc1_3.get(counter)); yield pi; counter++; } } return new List(generator); }

Finally calculating π

This was the hardest part because test cases were also approximation assertions. But as far as the entire List class implementation was done it can be used as:

console.log(List.PI.get(1)); // 3.333333333333333 console.log(List.PI.get(5)); // 3.1417411974336886 console.log(List.PI.get(12)); // 3.1415926497167876 console.log(List.PI.get(100)); // 3.1415926535897922

The higher the x value, the more precise the result will be.