Why does value of Pi stay the same after third iteration of Gauss–Legendre algorithm?

Question

I tried to write Gauss–Legendre algorithm in JS. I found algorithm here.

This is code i wrote:

let ao = 1;
  let bo = 1 / Math.sqrt(2);
  let to = 1 / 4;
  let po = 1;
  let an;
  let bn;
  let tn;
  let pn;
  let pi;
  for (let i = 0; i < 10; i++) {
    an = (ao + bo) / 2;
    bn = Math.sqrt(ao * bo);
    tn = to - po * Math.pow(ao - an, 2);
    pn = 2 * po;
    pi = Math.pow(an + bn, 2) / (4 * tn);
    console.log(pi.toFixed(60));
    ao = an;
    bo = bn;
    to = tn;
    po = pn;
  }

As I understand more iterations you perform a more accurate value of pi gets. But the problem is that after third iteration the value of pi stays the same. Here are the first three values I got.

3.140579250522168575088244324433617293834686279296875000000000

3.141592646213542838751209274050779640674591064453125000000000

3.141592653589794004176383168669417500495910644531250000000000

Why does value of Pi stay the same after third iteration of Gauss–Legendre algorithm?

JavaScript floating point numbers have 54 bits of mantissa, which is roughly 16 decimal digits. That's as much precision as you're going to get from the built-in number type. — Alexey Lebedev, Apr 03 '20 at 17:04
Compare `console.log(Math.PI)` and `console.log(Math.PI.toFixed(60))` — Alexey Lebedev, Apr 03 '20 at 17:06
`Math.PI.toFixed(60)` prints many more digits, but everything after 15th decimal place doesn't match the actual digits of PI, it's pure garbage. — Alexey Lebedev, Apr 03 '20 at 17:12
@AlexeyLebedev Yeah i see that now. Same is with my Pi Calculation. — Danilo Ivanovic, Apr 03 '20 at 17:14
@AlexeyLebedev Do you think if i create my own number type i could calculate even more digits? — Danilo Ivanovic, Apr 03 '20 at 17:17
@DaniloIvanovic absolutely, but it would be a lot of work. Maybe try looking for an existing library. — Alexey Lebedev, Apr 03 '20 at 17:26
https://jsfiddle.net/3cxbu52r/ - here I've converted your code to use `Decimal.js` library (https://github.com/MikeMcl/decimal.js). The algorithm gets to 60 digits of precision after 5 iterations. The result matches the real value of pi. — Alexey Lebedev, Apr 03 '20 at 18:07

score 1 · Answer 1 · answered Apr 03 '20 at 17:14

1

Your third iteration is correct to 15 significant decimal digits. Internally, Javascript represents all numbers as 64-bit double-precision floating-point numbers (also known as doubles), which can represent 15 to 17 significant decimal digits.

So I would say the result stays the same because the computer simply does not have any more precision to work with.

Converging to the (near-)maximum precision of the computer after three iterations is great! Good job!

answered Apr 03 '20 at 17:14

Joskar

600
5
12

I'm wondering why `.toFixed(60)` exhibits this strange behavior, pulling digits seemingly out of nowhere. And then starts padding with zeros exactly after 50 decimal places. – Alexey Lebedev Apr 03 '20 at 17:18
The "pulling digits seemingly out of nowhere" is due to the binary-to-decimal conversion. Some numbers in base-2 are not as easily representable in base-10. The number you have converged on (with the 64-bit double) apparently requires 52 decimal digits to represent exactly. But this does not mean that it has 52 digits of _accuracy_. It is still only _accurate_ to 15 to 17 digits. It is only a representational thing. – Joskar Apr 03 '20 at 20:46

Why does value of Pi stay the same after third iteration of Gauss–Legendre algorithm?

1 Answers1