[CLN-list] Question on algorithm for pi

[Bruno Haible]

Hi,

Barry Levin asked:
> I am not a programmer (yet), and I am doing a project for a Calculus class 
on 
> the derivation of pi. Since this software managed to produce a large amount 
> of digits for me, and although the code is open, I cannot see what it does 
> due to my own lack of skills, I would like to know how it calculates pi.

There are two methods:
  1) Special formulas leading to iterations that converge quadratically
     to pi.
  2) A more general technique for computing any elementary transcendental
     function's value quickly.

1) is more interesting from the mathematical point of view.
The source file cln/src/float/transcendental/cl_LF_pi.cc contains a few
algorithms that are all suitable for computing pi quickly. For an calculus
class, the classical Gauss AGM equality and convergence behaviour are most
interesting. (The equality is a transformation of definite integrals, and the
convergence involves power series.)

I recommend
    Jonathan M. Borwein, Peter B. Borwein: π and the AGM.
    Wiley 1987. Algorithm 2.2, p. 48.
It is a wonderful book.

2) This technique is more interesting for the computer algebra guy.
"Binary splitting" is a specialisation of the typical computer science
pattern "divide and conquer". Documented in cln/doc/ratseries.
Note that this technique has been extended to holonomic functions (not
only elementary functions) by Joris van der Hoeven, but his algorithms
are not implemented in CLN.

Bruno