Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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.

share|cite|improve this answer
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 6 '13 at 7: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 6 '13 at 8: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 6 '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 6 '13 at 17:30

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.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.