Accelerating approximations for arccos

Question

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 ?

Answer 1

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.