7
$\begingroup$

I have recently built a method to accelerate drastically the accuracy of the following approximation of $\arccos(x)$ :

$f_n(x)=2^n\sqrt{2-2g^{n-1}(x)}$ where $g(x)=\frac{1}2\sqrt{2+2x}$ and $g^n=g\underbrace{\circ\dots\circ}_{n\text{ times}} g$.

I would like to compare its converging speed to the one of another methods that seems to be based on the same principle, the Cohen-Villegas-Zagier acceleration for alternating series, which I do not know well at all.

Could someone please show me what the approximation of $\arccos(x)$ using the Cohen-Villegas-Zagier acceleration is ?

$\endgroup$
  • $\begingroup$ Are you looking for the algorithm laid out? The linked paper gives them. There just needs to be a bit of massaging to get $\arccos(x)$ to be in the right form... $\endgroup$ – aepound May 15 '15 at 0:54
  • $\begingroup$ @aepound Only Algorithm 1 is clear to me, and I suppose it isn't the fastest. Another algorithm is given later in the paper but, having not studied the whole paper, I do not fully get it. $\endgroup$ – Hippalectryon May 15 '15 at 13:34
  • $\begingroup$ Could you develop what you mean by the fact that you accelerated drastically the accuracy of $\arccos$? What was the rate of convergence before? What is your rate of convergence? $\endgroup$ – Beni Bogosel May 15 '15 at 18:57
  • $\begingroup$ @BeniBogosel By doing a weighted mean of $n$ approximation of $\arccos$, I get one approximation which has a gain in digits (that is, the number of correct digits gained) compared to the most precise of the approximation used in the weighted mean that is a second degree polynomial; for instance for $n=30$ I win about $380$ digits, for $n=150$ I win about $7000$ digits. $\endgroup$ – Hippalectryon May 15 '15 at 19:31
2
+300
$\begingroup$

Well, I'll show you where I was able to get, but I wasn't able to push through it all to the end. Maybe it will get you close enough that you could go from there.

The paper by Cohen, Villegas, and Zagier (linked above) works on series of the form $$ S = \sum_{k=0}^\infty (-1)^k a_k. $$ Though they state that "$a_k$ is a reasonably well-behave function, which goes slowly to $0$ as $k\rightarrow\infty$." Whether $\operatorname{acos}()$ behaves like this, well, that's another question that I'm blatantly disregarding at the moment.

Van Wijngaarden has a transform to convert a positive series summation into an alternating one $$ \sum_{r=1}^\infty v_r = \sum_{r=1}^\infty (-1)^{r-1}w_r, $$ where $$ w_r = v_r + 2v_{2r} + 4v_{4r} + \dots. $$ (I got this from "Numerical Recipes in C" as referenced in the linked paper above) It states that

Since,$\ldots$ [the indices] increase tremendously rapidly, as powers of 2, it often requires only a few terms to converge [$w_r$] to extraordinary accuracy.

So, to utilize this, we need to convert $\operatorname{acos}()$ into an alternating series. From wikipedia we get that $$ \operatorname{acos}(z) = \frac{\pi}{2} - \sum_{n=0}^\infty \binom{2n}{n}\frac{z^{2n+1}}{4^n(2n+1)} $$ Then we can use the transform above to get $$ \begin{split} \frac{\pi}{2} - \operatorname{acos}(z) &= \sum_{n=0}^\infty \binom{2n}{n}\frac{z^{2n+1}}{4^n(2n+1)}\\ &= 1 + \sum_{n=1}^\infty \binom{2n}{n}\frac{z^{2n+1}}{4^n(2n+1)}\\ &= 1 + \sum_{r=1}^\infty (-1)^{r-1}w_r, \end{split} $$ where $$ \begin{split} w_r &= \sum_{k=0}^\infty2^k\binom{2^{k+1}r}{2^kr} \frac{z^{2^{k+1}r+1}}{4^{2^kr}\left(2^{k+1}r+1\right)}\\ &= \sum_{k=0}^\infty\binom{2^{k+1}r}{2^kr} \frac{2^kz^{2^{k+1}r+1}}{2^{2^{k+1}r}\left(2^{k+1}r+1\right)}. \end{split} $$ Let $\alpha(r) = 2^{k+1}r + 1$, then we can write $$ w_r= \sum_{k=0}^\infty\binom{\alpha(r)-1}{\frac{(\alpha(r)-1)}{2}} \frac{z^{\alpha(r)}}{2^{\alpha(r)-k}\left(\alpha(r)\right)}. $$

So, we have $$ \begin{align*} \frac{\pi}{2} - 1 - \operatorname{acos}(z) &= \sum_{r=1}^\infty (-1)^{r-1}w_r & w_r &= \sum_{k=0}^\infty\binom{\alpha(r)-1}{(\alpha(r)-1)/2} \frac{z^{\alpha(r)}}{2^{\alpha(r)-k}\left(\alpha(r)\right)}. \end{align*} $$ So, we want to accelerate the calculation of the sum in the left equation.

Now, the second algorithm in Cohen et. al is given as

Algorithm 2

  1. Let $Q_n(X) = \sum_{k=0}^nb_kX^k$
  2. Set $d = Q_n(-1)$
  3. Set $c = -d$
  4. Set $s = 0$
  5. For $k=0\:\text{to}\: n-1,$

    $c = b_k - c$

    $s + c\cdot a_k$

  6. Output $s/d$.

They specify in the paper that you should let $Q_n = B_n = P_n^{(m)}/((n-m)(m+1)!2^m)$. It was here that I had to stop.

I did find another explanation of the Cohen et al. acceleration, although it's explanation is not very in depth. You can find it (along with a postscript version) here. Good luck.

$\endgroup$
  • $\begingroup$ Thanks, that's really useful. The last link also made me know the Richardson extrapolation, which seems be closer to my method and probably more relevant for a comparison. $\endgroup$ – Hippalectryon May 15 '15 at 21:58
  • $\begingroup$ Great to hear it was useful. :) $\endgroup$ – aepound May 15 '15 at 23:05
  • 2
    $\begingroup$ I like your usage of nested quotation to format pseudocode of algorithm 2. $\endgroup$ – VividD May 15 '15 at 23:39
  • $\begingroup$ @VividD, Thanks! I didn't want to see if the LaTeX packages algorithm, algorithmic, etc. were loaded by MathJax... :) $\endgroup$ – aepound May 15 '15 at 23:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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