4

The Chudnovsky algorithm based on hypergeometric series seems to appear prominently. Why are approaches based around $\arctan$ slower?

Is there some intuitive, conceptual description of the "redundancy" or inefficiency in $\arctan$ based calculations that explain why they are slower?

user782220
  • 3,195

2 Answers2

1

Sure, the coefficients in the power series of $\arctan$ are $\sim\frac1n$, hence decrease very slowly. So to compute $n$ digits of $\arctan x$ with $x\approx 10^{-k}$, you need $\frac nk$ summands.

Hagen von Eitzen
  • 374,180
  • 1
    You don't need to use $\arctan 1$ as your basis. Look at Machin's formula for example, which is based on the fact that $$\frac{\pi}{4} = 4\arctan\frac15 - \arctan\frac{1}{239}$$ – mrf Mar 06 '13 at 07:55
  • @Hagen But philosophically why "should" the power series of $\arctan$ be converging like $\frac{1}{n}$ and not converge faster. I am asking is there a way of understanding why some series converge faster, other than we tried a bunch randomly and Chudnovsky happens to have very fast convergence and its fast just because that's the way it just happened to end up. – user782220 Mar 06 '13 at 08:02
  • @mrf Ye3s, sure. So one $x$ is $\frac 1{239}\approx10^{-3}$, thus you need only about 350000 summands for 1000000 digits. The other summand has $x\approx 10^{-1}$, so we need about one summand per digit (in fact more as $5$ is signoificantly smaller than $10$). – Hagen von Eitzen Mar 06 '13 at 17:26
  • @user782220 Of course the power series of arctan "should" behave exactly the way we prove it does. :) – Hagen von Eitzen Mar 06 '13 at 17:30
0

If you want to calculate a number z, you may calculate it using the Taylor formula if you can express z as z = f (x), where f (x) and all its derivatives can all be calculated easily, and you usually gain a fixed number of digits at each iteration (unless x is close to the border of the circle where the Taylor formula converges).

You may find a function where z is the solution of f (z) = 0, and you can either use the Newton scheme, or some other approximation scheme if f' is hard to calculate, and double the number of digits at each step. Of course you have to find a function where f (z) can be calculated with the required precision.

Take sqrt (2). You can use the Taylor formula for sqrt (x) around x = 1.414^2, for example, which will converge at maybe three digits per round. Or you use the Newton formula for f (z) = z^2 - 2 and the number of digits doubles on each iteration.

gnasher729
  • 10,113