Karim BELABAS on Wed, 15 Jan 2003 16:52:24 +0100 (MET) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Pi |
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/