From: Clive Tooth Subject: Re: More on Pi and randomness Date: Sun, 21 May 2000 20:57:43 +0100 Newsgroups: sci.math,sci.crypt Summary: [missing] "Trevor L. Jackson, III" wrote: > Guy Macon wrote: > > > In article <3925A7F2.65BB788B@eton.powernet.co.uk>, binary@eton.powernet.co.uk wrote: > > > > >I understand the Nth hexit of pi, irrespective of the value of N, to be > > >calculable using the equation derived by Borwein, Borwein and Plouffe. > > >The 400 billionth hexit of pi has been thus calculated. > > > > Really?!? (not questioning you, just suprised). Does the time to compute > > the answer get larger as N gets larger? Linearaly? Exponentialy? > > Since the formula is based upon N, it's implementation grows as the log of N. No. The time required to calculate the Nth _hex_ digit of pi by these non-memory-intensive methods is at most O(N*(log(N))^O(1)). The time required to calculate the Nth digit of pi in an arbitrary base by non-memory-intensive methods is at most O(N^3*(log(N))^O(1)). Some interesting things about these methods (for values of N typically attempted): 1) The amount of memory required is small compared to the typical memory on today's PCs. 2) Little or no multiprecision arithmetic is required. 3) Computing _all_ the hex digits of pi, from 1 to N, using the fastest known method (whose memory usage is O(N)) is asymptotically faster than using the fastest known non-memory-intensive method to just calculate the Nth digit. There is a distributed processing project, PiHex, to compute the quadrillion (=10^15) th bit of pi: http://www.cecm.sfu.ca/projects/pihex/index.html The base formula for that project is described at http://www-stud.enst.fr/~bellard/pi/pi_bin/pi_bin.html Some time ago I posted an explanation of how these Nth hex digit methods work. Deja cannot seem to find it now so I reproduce it here. ================================================================= Subject: Re: digit extraction algorithms for pi Date: Thu, 14 Jan 1999 22:41:04 +0000 From: Clive Tooth Newsgroups: sci.math Tom Weston wrote: > I've just been reading about the above algorithms, in particular > the Bailey-Borwein-Plouffe method, on the world wide web and am > rather puzzled about one aspect. > > As I understand things, the algorithm is based upon the expression > > pi= sum_{0}^{\infty} (4/(8n+1) - 2/(8n+4) - 1/(8n+5) -1/(8n+6)).(1/16)^n > > from which apparently you can extract the nth digit without the need to > calculate any of the previous. What puzzles me is how precisely is this > is done. > > If the coefficients of the (1/16)^n were integers less than 16 then > clearly the digits would be these numbers. Since it isn't, I imagine you > will need to evaluate at least a few of the terms. > > Is there an easy way to see how this is done? It seems that the when > the coefficient is written as a single fraction then the denominator must > be a multiple of 8 and that the coefficients lie in the range 0 to 47/15 > but I can't quite see how to use this to get the digit. The method is not quite as straightforward as you might have hoped but it is fairly simple. It uses no multiprecision arithmetic - 64 bit floating point will be sufficient for interestingly large values of n (the hex digit required). I follow (but shorten) the exposition in "On the Rapid Computation of Various Polylogarithmic Constants" by D H Bailey, P B Borwein and S Plouffe, Mathematics of Computation 66 (1997), 903-913. In particular, see that paper for a discussion of the accuracy of floating point arithmetic required: 64 bit or 128 bit. First of all, note that, if a and b are positive integers, we can calculate a^b mod c in less than 2logbase2(b) multiplications by the usual method (which can be related to the binary representation of b). Thus to calculate a^25, for example, we evaluate a^2, a^3, a^6, a^12, a^24, a^25. All multiplications being done mod c. Consider a constant, S, defined by a series of the form S = sigma(k=0, +infinity)[1/((b^(c*k))*p(k))] where b and c are positive integers, and p(k) is a polynomial with integer coefficients. Note that the digits in the base b expansion of S, beginning at position n+1, can be obtained from the fractional part of S*b^n. So: S*b^n mod 1 = sigma(k=0, +infinity)[b^(n-c*k)/p(k) mod 1] = sigma(k=0, floor(n/c))[(b^(n-c*k) mod p(k))/p(k) mod 1] + sigma(k=floor(c)+1, +infinity)[b^(n-c*k)/p(k) mod 1] For each term of the first summation, the binary exponentiation scheme is used to evaluate the numerator. Then floating point arithmetic is used to perform the division and add the result to the sum mod 1. The second summation, where the exponent of b is negative, may be evaluated, as written, using floating point arithmetic. It is only necessary to compute a few terms of this second summation, just enough to ensure that the remaining terms sum to less than the "epsilon" of the floating point arithmetic being used. The final result, a fraction between 0 and 1, is then converted to the desired base b. For pi, this algorithm is slightly slower [by a factor log(log(log(n)))] than the very fastest known algorithm which calculates all the digits up to and including the nth. However, that algorithm uses Strassen-Schönhage multiplication - which nobody seems to use in high precision computations of pi, preferring the slightly slower but easier FFT methods. ================================================================= -- Clive Tooth http://www.pisquaredoversix.force9.co.uk/ End of document