Re: Pi

[Karim BELABAS <Karim.Belabas@math.u-psud.fr>]

On Wed, 15 Jan 2003, Ralf Stephan wrote:
> Karim Belabas wrote
> > On Tue, 14 Jan 2003, Bill Allombert wrote:
> > > If it is your question, there is no incremental algorithm to compute Pi
> > > implemented.  Computing Pi at 12200 d.p does not use the knowledge of the
> > > first 12000 d.p.
>
> Yes, I was thinking about Bailey/Borwein/Plouffe before having read them,
> BBP is O(n\log^3n) for the nth digit but constpi() is[*] faster so...
>
>>> I do not know if it would make sense to do that.
>>
>> It definitely would, using the log((1+i) / 2) expansion. I don't think it
>> would have a major effect on running times, but if somebody wants to try it...
>
> Now, if it wouldn't have a major effect, scratch it. I have the impression,
> to fully understand the constpi() code I will have to do a little more
> reading/writing.

/* Chudnovsky's formula:
 *                         ----
 *  53360 (640320)^(1/2)   \    (6n)! (545140134 n + 13591409)
 *  -------------------- = /    ------------------------------
 *        Pi               ----   (n!)^3 (3n)! (-640320)^(3n)
 *                         n>=0
 */

(just added to the source code:-)

> > Also, a different Pi formula needs to be implemented [ the current one
> > was chosen so that almost all multiplication/divisions involve a single
> > precision operand, which is not at all what we want now ! ].

Actually, scratch this. The same formula with binary splitting + GMP
FFT-based multiplication should do the trick.

    Karim.
-- 
Karim Belabas                    Tel: (+33) (0)1 69 15 57 48
Dép. de Mathématiques, Bât. 425  Fax: (+33) (0)1 69 15 60 19
Université Paris-Sud             Email: Karim.Belabas@math.u-psud.fr
F-91405 Orsay (France)           http://www.math.u-psud.fr/~belabas/
--
PARI/GP Home Page: http://www.parigp-home.de/