Re: How to calculate pi in binary ?

From: François Charton (fcharton_at_carthage.fr)
Date: 09/30/04 

Date: Thu, 30 Sep 2004 17:21:02 +0200

"The Last Danish Pastry" wrote
>
> In fact, it is less efficient than the best ones available when it comes
to
> calculating just the Nth digit of pi. To calculate the Nth binary digit of
> pi two possible methods are:
>
> 1) Use the formula which you give.
> 2) Compute the first N digits by the fastest known algorithm and then
> discard N-1 of them.
>
> According to ["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] method (2) is slightly faster.
>

Are you sure about that? The article you mention says : "This algorithm is
by a factor log(log(log(n))) asymptotically slower than the fastest know
algorithms ..." and "Of course, this complexity analysis is totally
misleading: the strength of our algorithm rests mostly on its easy
implementation in standard precision without requiring FFT methods to
accelerate the implementation".

Note that the authors are talking asymptotic complexity here, not actual
speed... Also, the very low value of log(log(log(n))) (for any value of n
accessible to current calculators, ie n in the billions range, this is quite
negligible) means that the constant term in the complexity analysis will
probably be, in real world situations, the important factor in comparing
both algorithms... This, in turn, will depend on the methods of calculation
(number of operations) and memory used, and the BBP algorithm is pretty sure
to be much simpler on both counts.

Finally, several improvement on the BBP formula have been proposed, one of
the, by F. Bellard, is almost twice as fast as the original BBP algorithm.

I might be wrong, but my impression is that the situation is the same as
with many asymptotically faster algorithms (eg Strassen algorithm for matrix
multiplication). As the number of digits to be calculated increase, they
actually become faster than other methods, but their high constant term (due
to calculation complexity or memory usage) make their practical
implementation slower than these "asymptotically worse" methods, for the
values of N currently accessible.

Francois

Relevant Pages

  • Re: General Opinion on a how to?
    ... So different prize ... not have to change the database as you add new algorithm to the system. ... The way i see my calculation working with the aid of Jameys tips is this: ... Load into a prize pool object instance for that game ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: No Set Contains Every Computable Natural (was Church-Turing compared to Zuse-Fredkin thesis)
    ... Russell is right about Turing saying this, ... You might not want to call this an algorithm which has ... decimal representation of x digit by digit. ...
    (comp.theory)
  • Re: Kresss Probability Trilogy Qs
    ... We know our mathematics is true by direct insight, ... Any calculation has an experimental aspect to it (albeit one that is ... objections and answers which I'm ... Our "algorithm" is an ...
    (rec.arts.sf.science)
  • Re: Powers and logic
    ... quasi wrote: ... It is easy to give an algorithm which could be calculated ... one can always find the leading digit by inspection. ... The space requirement would exceed the capacity of ...
    (sci.math)
  • Re: Large-numbers division way too slow -- what to do?
    ... > algorithm is now responsible for most of the slowness. ... I want to return the quotient or the remainder). ... In the division function, at the very bottom, I placed: ... processing the last digit becomes the remainder. ...
    (sci.crypt)
Quantcast