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.