Hacker News Reader

Comment by dpayne | Hacker News Reader

Great article on the complexities of investigating performance issues! Another very interesting surprise is when I run this locally on my macbook, clang is much faster

  mac >> go run main.go
  approximating pi with 1000000000 iterations.
  3.1415926545880506
  total time taken is: 9.706911232s

  mac >> clang++ -O3 -ffast-math -march=native main.cpp
  mac >> ./a.out
  3.1415926545864963
  total time taken is: 2.14196s

View on HN

The speed of the answer doesn't matter so much when the answer is wrong. And (after checking Google) BOTH of those are wrong. :/

Recompiling without fastmath gives the same answer as the article "3.1415926545880506".

  mac >> clang++ -O3 -march=native main.cpp
  mac >> ./a.out
  3.1415926545880506
  total time taken is: 4.3861569999999999s

Twice as slow as the fastmath version but still faster than the go version.

Clearly the two results are different, so something strange is going on. But you need to define wrong, consider incrementally approximating pi in 7 steps:

  100,50,25,12,4,2,3,3.5
  > 3.5

Or even:

  100,90,80,70,60,50,40
  > 40

I'm assuming you mean wrong as in the algorithm implemented with arbitrary precision would en up with a different set of digits for the number of iterations given? Or something along those lines?

Oh, I mean they're both wrong in the 10th position even though they agree. But it is curious that they diverge after that.

It's probably more a problem of the algorithm not calculating significant figures and truncating the answer.

The algorithm is computing an alternating series, with the largest n being 5x10^7. The error in an alternating series (when the sequence is strictly decreasing in absolute value) is the absolute value of the next term. This is 4/(2*(5x10^7 + 1) + 1), which is a bit less than 4x10^-8, so we would only expect 7 digits to be correct. In fact, it is the 8th digit which goes awry (not the 10th): it should be a 5 rather than a 7.

This particular series, which comes from a series for the arctan of 1, has very slow convergence. An easily better one is Machin's formula, which converges faster than a geometric series (that is, the number of terms needed is at most linear in the number of wanted digits).

However, according to math.pi in python3.3 the second number (with higher number of iterations) is closer to pi than the lower iteration number.

So is it possible that the algorithm doesn't converge to correct digits for so "few" iterations?

Reply on news.ycombinator.com