MathGroup Archive 2000

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Transformation Methods for Pi

  • To: mathgroup at smc.vnet.net
  • Subject: [mg22414] Re: Transformation Methods for Pi
  • From: Mark Sofroniou <marks at wolfram.com>
  • Date: Wed, 1 Mar 2000 00:40:07 -0500 (EST)
  • Sender: owner-wri-mathgroup at wolfram.com

sniff wrote:

> In Mathematica 4, the usage of N[Pi,10000000] (with $MaxPrecision =
> Infinity) strongly suggests that the people at Wolfram Research are still
> not using the best way to calculate Pi. It is very slow. Are they still
> using a calculus based method (such as arctan functions) to compute this
> number? On my old NT system, 8,388,608 digits of Pi are calculated in 2,851
> seconds when using compiled C code of a transformation method and FFT to
> speed up multiplications. Using Mathematica 4, I terminated the calculation after 17
> hours. - It was still not done.
>
> Where can I find more information regarding Mathematica 4 and its way to
> compute Pi.
>
> GTO

Mathematica uses a Ramanujan sum found by the Chudnovsky brothers
in order to compute a numerical approximation to Pi. In version V4.0
the sum is evaluated using binary splitting which takes advantage of
asymptotically faster multiprecision multiplication methods.

The following web page contains several papers describing the the method
of binary splitting and its application to the Chudnovskys' formula for Pi.

http://xavier.gourdon.free.fr/Constants/constants.html

This is by far the fastest known method to approximate Pi numerically,
even in the billion digit range, as you can see at the following page.

http://xavier.gourdon.free.fr/Constants/PiProgram/pifast.html

The program pifast uses a Fast Fourier Transform method which
performs things like swapping parts of the computation to disk,
which are operating system dependent tasks. We are currently
looking at ways of extending the range of computations in
Mathematica in a platform independent manner.

There are three things that you can do when you want to work
with very high precision numbers.

1) Set $MaxPrecision = Infinity.

2) Use Developer`SetSystemOptions to set "TimesExtraMemoryLimit".
The default value limits the maximum amount of memory that is used
in Fast Fourier Transform multiplication. The value in V4.0 is:

In[1]:= Developer`SystemOptions["TimesExtraMemoryLimit"]

Out[1]= TimesExtraMemoryLimit -> 34000000

If you have more memory in your machine you can add a line
like the following to your init.m. This sets the maximum amount
of memory to 256 MB.

Developer`SetSystemOptions["TimesExtraMemoryLimit"->256*^6];

Above this value the computation is recursively broken up using
Karatsuba (3 for 4) multiplication with FFT multiplication for
the sub-blocks.

3) You can tune the crossover value at which FFT multiplication
takes over from Karatsuba multiplication in order to take into
account things like the amount of primary and secondary level cache
that your machine has. The function:

Experimental`FindTimesCrossoverDigits[]

finds a value that can be set with a line like this in your init.m
file:

Developer`SetSystemOptions["TimesCrossoverDigits"->6000];

Using these settings, 8,388,608 digits of Pi can be computed in
around 2427.64 seconds on a Pentium II 450 Mhz with 256MB RAM
running RedHat Linux 5.2.

You should be careful to include a semicolon at the end of a line
(e.g. Timing[np = N[Pi, 8388608];]) otherwise you will also be
including time to convert the number from binary to decimal.
Printing such large numbers is not completely optimised in version
4.0 and can take considerably longer than the time to approximate Pi
numerically.

Mark Sofroniou,
Research and Development,
Wolfram Research Inc.




  • Prev by Date: Re: Simplifying Problems
  • Next by Date: Re: Simplifying Problems
  • Previous by thread: Re: Simplifying Problems
  • Next by thread: Re: J/Link Examples ??