Contents : + Introduction + Version + Timings + Number of digits + Usage + Behavior of the program + Formula and algorithm used + Problems + What should be done for next versions + Source code information + Conclusion ================ | Introduction | ================ PiFast computes decimal digits of Pi and E. The default output are the files pi.txt and e.txt. PiFast currently holds the world record pi computation on a home computer with 9.5 billion digits (Shigeru Kondo, on a Pentium III 800, 1024 Mo of memory). PiFast can compute much more digits than what could fit in the physical memory. PiFast33 is available on several platforms, download it from the page http://xavier.gourdon.free.fr/Constants/PiProgram/download.html Windows 95/98 and NT : download the file pifast.zip hpux10.20 : download the file pifast_hp.gz irix6.2 : download the file pifast_irix.gz aix4.3.2 : download the file pifast_aix.gz =========== | Version | =========== PiFast33 is Version 3.3 of PiFast (released on Jul 08 2000). New features of version 3.3 : * PiFast33 computes also the number e = exp(1). Two methods are available. * PiFast can verify a pi computation by using the Fabrice Bellard formula which computes directly the n-th bit of pi. * A bug (reported by Shigeru Kondo for some computations with more than 6 billion digits) have been corrected. * PiFast is now available on unix platforms. * The PiFast.log file, generated if problems are encountered, has been enriched. More internal tests are done. * The default output format is now a classical format (Guttenberg) Older versions +++++++++++++ Version : 3.2 (released on Dec 27 1999) ------------- * A larger number of digits can be computed with a limited physical memory in the advanced disk memory mode. * Timings have been decreased by a few percents, especially in the standard mode. * Physical memory needed has been decreased by a few percents (~ 4%). * A Sqrt(2) computation is available (with verification). This mode essentially permits to test PiFast32 with a huge number of digits, with ranges that I cannot reach with my computer. The timings of Sqrt(2) computation is at least ten times faster than the pi computation. * When errors of the program are encountered (I hope this does not happen, but since I could not test PiFast in huge ranges, bugs can appear...), a PiFast.log file is generated. This file contains information about the program and the error and should be send to xavier.gourdon@free.fr to help me to debug the problem. * When reading a compressed format, the program can generate x digits every y digits, where x and y are user specified. Large number of digits computation with version 3.2 : > 6,442,450,944 digits on a PIII 700 (1024 Mo) (Jan 13 2000) in 286 hours by Shigeru Kondo (world record on home PC at that time) The result has been checked with a beta version of PiFast33 containing the Fabrice Bellard formula check. > 1,610,612,736 digits on a Athlon 600 (and only 128 Mo) (Mar 23 2000) in 126 hours by Colin Martin. This is a world pi record computation on a PC with only 128 Mo of memory. > 805,306,368 digits on a Athlon 600 (and only 128 Mo) (Jan 20 2000) in 53 hours by Colin Martin. Version : 3.1 (released on Oct 30 1999) ------------- This version contains several improvements, essentially dedicated to huge computations (1 giga digits or more). * A new disk swap mode exists, using a Number Theoritic Transform (NTT) with a variable number of primes, that permits to have a quasi-linear behavior of the timings of the program for really huge computations (to be compared with the asymptotic quadratic behavior of PiFast23). * The maximum number of digits to be computed with that version is now 24 billions digits (instead of 4.5 billions with version 2.3) in the disk swap mode. In this respect, developpement have been made to limit the internal swap files size to 2 giga-bytes (by generating several files if needed). * The output can be directly compressed by PiFast32. The resulting file can be read (to access digits at some places only for example) or transformed into a standard one with PiFast. Different output format are also available in this compressed output mode. Large number of digits computation with version 3.1 : > 9,500,000,000 digits on a PIII 800 (1024 Mo) (May 07 2000) in 459 hours by Shigeru Kondo (world record on home PC at this date) The result has been checked with a beta version of PiFast33 containing the Fabrice Bellard formula check. > 8,000,000,000 digits on a PIII 750 (1024 Mo) (Apr 28 2000) in 384 hours by Shigeru Kondo (world record on home PC at that time) > 4,294,960,000 ( ~ 2^32 ) digits on a PIII 550 (1024 Mo) (Nov 13 1999) in 246 hours by Shigeru Kondo (world record pi computation on PC at this date). > 268,435,456 (=256 * 2^20) digits on a PII 300 (128 Mo) (Dec 15 1999) in 25.5 hours by Stuart Lyster. Version : 2.3 (released on Sep 5 1999) ------------- PiFast23 is Version 2.3 of PiFast. This new version contains a few number of improvements : * A difficult bug (reported to me by Shigeru Kondo) was found that made version 2.2 going wrong when FFT size was >= 4096k (possible on machines with 256 Meg at least). * The maximum number of digits to be computed with that version is now 4.5 billion digits (instead of 1.5 billion with version 2.2). Large number of digits computation with version 2.3 : > 2,684,354,560 ( = 2.5*2^30 ) digits on a PIII 550 (1024 Mo) (19 Oct 1999) in 245 hours by Shigeru Kondo (world record pi computation on PC at this date). > 2.1 billions digits on a PIII 350 (1024 Mo) (13 Sep 1999) in 157 hours by Shigeru Kondo. Version : 2.2 (released on 10 Aug 1999) ------------- PiFast22 is Version 2.2 of PiFast. Efforts have essential been made in the disk swap mode. Here are the new features of version 2.2 * In the disk swap mode, Disk swapping has been reduced, saving a quite large part of the total timing. * Disk swap timings are given in the computation information summary (in the header of the resulting file). * Disk head movements are reduced. * A bug has been fixed to have all computed digits right (in some cases with version 1.1 and 2.1, the 0.8% last digits were wrong). Another bug in internal computation has also been fixed. * Physical memory needed has been decreased by 5% in the disk memory mode. * Documentation has been enlarged (behavior of the program). Large number of digits computation with version 2.2 : > 268,435,456 (=256 * 2^20) digits on a PII 300 (128 Mo) (13 Aug 1999) in 32.7 hours by Stuart Lyster. Version : 2.1 (released on 5 Aug 1999) ------------- PiFast21 is Version 2.1 of PiFast. This version has new features : * It can use disk memory to perform huge computations. * A bug has been fixed than permits to reach a larger number of digits. * A large computation using disk memory can be done in several runs. * A computation information summary is written as the header of the resulting file. Large number of digits computation with version 2.1 : > 1.5 billion digits on a PIII 550 (1024 Mo), by Shigeru Kondo in 119 hours (29 Aug 1999). > 1 billion digits on a PIII 550 (1024 Mo), by Shigeru Kondo in 63.5 hours (13 Aug 1999). > 256 millions digits on my PII 350 (128 Mo) (6 Aug 1999) in 41 hours. Version 1.1 (released on 30 jul 1999) : ----------- * Faster than the first version of PiFast (15%) * Less memory consuming Large number of digits computation reported to me with version 1.1 : > 128 Mega (134217728) decimal digits on a PIII 600 (1024 Mo), by Shigeru Kondo in 2 hours and 45 minutes (4 Aug 1999). > 64 Mega (67108864) decimal digits on a pII 300 (128 Mo) in 8 hours and 18 minutes, by Stuart Lyster (30 jul 1999). Version 1.0 (First Version) was released on 17 jul 1999 : ----------- Large number of digits computation reported to me with version 1.0 : > 64 Mega (67108864) decimal digits on a pII 300 (128 Mo) in 19 hours 12 minutes, by Stuart Lyster (21 Jul 1999). =========== | Timings | =========== PiFast33 is the fastest program to compute Pi on the net on Windows (Jul 08 2000). It is twice faster as the fastest program I have found on the net (pi_agm_23 by Carey BloodWorth). See also the page http://home.istar.ca/~lyster/pi.html for the current fastest pi programs on PC. I have not been able to perform comparisons on unix platforms. Notice that PiFast on unix is not as tuned as on windows. For example, PiFast on windows uses basic routines handling bytes in the little-endian conventions, this has not been tuned in the big-endian convention for most unix machines. Following are just sample of timings. More can be found from PiFast home page : http://xavier.gourdon.free.fr/Constants/PiFast/pifast.html Send me your timings on other machines ! Standard mode (no disk space used) ------------- This mode is the fastest when there are enough physical memory. Timings sample on a PIII 700 with 512 Mo running on Windows NT: PI Computation : 1 Million decimal digits : 17.67 seconds 2 Million decimal digits : 41.08 seconds 4 Million decimal digits : 93.9 seconds 8 Million decimal digits : 207.36 seconds 16 Million decimal digits : 499.22 seconds 32 Million decimal digits : 1127 seconds 64 Million decimal digits : 2605 seconds 128 Million decimal digits : 6836 seconds E Computation : 1 Million decimal digits : 6.77 seconds 2 Million decimal digits : 14.86 seconds 4 Million decimal digits : 33.86 seconds 8 Million decimal digits : 70.4 seconds 16 Million decimal digits : 158.5 seconds 32 Million decimal digits : 358 seconds 64 Million decimal digits : 741.6 seconds 128 Million decimal digits : 2262 seconds Standard Disk memory mode ------------------------- This mode is be used for very large computation when the standard mode requires too much physical memory. It only requires a few disk space. (timings with version 2.3, on my Pentium 350 with 128M of physical memory) 32 millions decimal digits : 3662 seconds (~ 1 hour 1 minutes) 64 millions decimal digits : 9829 seconds (~ 2 hours 44 minutes) 128 millions decimal digits : 30320 seconds (~ 8 hours 35 minutes) 256 millions decimal digits : 110000 seconds (~30 hours 30 minutes) Disk memory mode for huge computations -------------------------------------- This mode is the fastest for huge computations. It requires largest disk space. (timings with version 3.1, on my Pentium 350 with 128M of physical memory) 128 millions decimal digits : 28400 seconds (~ 7 hours 53 minutes) 256 millions decimal digits : 67900 seconds (~18 hours 52 minutes) Important : the timings in the disk memory use mode are sensitive to your disk access speed. ==================== | Number of digits | ==================== Standard mode (no disk space used) ------------- The maximum number of decimal digits you can compute with PiFast in standard mode depends essentially of the amount of your physical memory. Several low memory modes enable to compute a very large number of digits. But when you want a large number of digits, you should use the disk memory mode instead of a very low memory mode in standard mode. (The threshold depends on the hardware configuration. On my 128M machine, it is between 16 and 32 millions of digits). With version 1.1, which ran only in standard mode, Stuart Lyster has reported me a 64 millions digits computation on a 128M machine. It is strongly recommended that you work only with physical memory (disk swapping gives very poor results) in this mode. Disk memory use mode -------------------- Two mode of this type exists (a special disk memory mode can be used for really huge computations). This mode permits to reach a very large number of digits. The program can potentially compute a bit more than 24 billion digits (which is more than the 4.5 billion limitation of version 2.3) independantly of the physical memory available (but a large physical memory amount is better to have not too bad timings), but no practical tests have been done up to this value direction (the largest number of digits tested is 9.5 billion digits with PiFast31). The 24 billions limitation is due to the maximum value 2^31 on the long C type (in various places in the program). I would appreciate any comments on a very large number of digits computation experience with PiFast (xavier.gourdon@free.fr). ========= | Usage | ========= Run PiFast33.exe in a dos window (or in a unix shell window for unix versions. You may type chmod +x PiFast33 before running it). Usage information about running PiFast33 can be found in the help.txt file (avalaible at http://xavier.gourdon.free.fr/Constants/PiProgram/download.html) =========================== | Behavior of the program | =========================== Memory : In standard mode, the required physical memory by PiFast to compute N decimal digits of Pi using and FFT of size NFFT is approximately Physical memory (in bytes) = 2*N + 40*NFFT. In the disk memory mode, memory required is Physical memory (in bytes) = 48*NFFT Disk memory (in bytes) = 2*N In the disk memory huge mode, memory required is Physical memory (in bytes) = 48*NFFT Disk memory (in bytes) ~ 4.5*N (approximation) (The preceeding PiFast help file had 4*N instead of 4.5*N in the last term. This is not a different behavior of PiFast but just a correction in the documentation, since 4*N was a little too optimistic). Note that the Disk memory requirement during the computation is also enough to contain the final output files. The e computation behaves in the same way, expect in the disk memory huge mode where it uses only 3.5*N byte space on the disk. Timing : In the fastest mode (until you do not reach your physical memory limit), PiFast is close to linear. That is, when you double the number of digits to be computed, your timing almost doubles (in fact, the practical factor is often 2.2 or 2.3). Things are getting worse once your physical memory is full : the program becomes asymptotically quadratic (that is, for huge number of digits, the timing has a factor of 4.) Timings in the standard disk memory mode on my 128M machine show a factor of 2.7 between the 32 and 64 millions computation, a factor of 3.1 between 64 and 128 millions, a factor of 3.6 ~ 3.7 between 128 and 256 millions. The asymptotic behavior is much better in the second disk memory mode, dedicated to huge computations. The theoritical behaviour in this latest mode is of the form T = n log(n)^3 + alpha * n^2, with alpha very small. In practical computations, the alpha*n^2 part is so small that it should not be representative (it correspond to the chinese remainder theorem in the NTT when the number of primes is large). Number of digits : Due to how I do things, the program has a (small) threshold when the number of digits required is close to a power of two (for example, on my machine, computing 1048576 digits takes 48 seconds, computing 1040000 digits takes 44 seconds : nearly 10% time saved with 0.8% less digits). This remark is important since power of two number of digits is often used to compute pi (PiFast does not need power of two digits). For that reason, I personnaly compute pi with PiFast with 1 million digits (instead of 1Mega = 1048576), 2millions, 4, 8 ... ============================== | Formula and Algorithm used | ============================== PiFast is based on Ramanajun like formula. The Chudnovsky method is based on the Chudnovsky formula ---- 426880 (10005)^(1/2) \ (6n)! (545140134 n + 13591409) -------------------- = / ------------------------------ Pi ---- (n!)^3 (3n)! (-640320)^(3n) n>=0 which adds roughly 14 decimal digits by term. The Ramanujan method is based on the Ramanujan formula ---- 1 \ (4n)! (1103 + 26390 n) ---- = 2 (2)^(1/2) / ----------------------- Pi ---- 4^(4n) (n!)^4 99^(4n+2) n>=0 which adds roughly 8 decimal digits by term. From these formulas, the algorithm used is the Brent binary splitting acceleration together with an efficient cache handling hermitian FFT to multiply big integers. Details of the binary splitting method can be found on my web site : http://xavier.gourdon.free.fr/Constants/Algorithms/splitting.html Note : This approach has a theoritical complexity of O(n log(n)^3) to compute n digits of Pi. The AGM techniques (Gauss-Salamin or Borwein Quartic algorithm for example) have an asymptotically better complexity of O(n log(n)^2). Nethertheless these theoritical bounds are not practical (non cached-memory access and data trashing make the practical complexity higher) and the constants on front of the big O are important. My 10 years experience on the subject have shown me that for a reachable number of digits on actual machines, a well handled binary splitting approach from Chudnovsky formula is better than any other known method. For more detailed information about computation of mathematical constants with a large number of digits, go to http://xavier.gourdon.free.fr/Constants/constants.html Pi verification with Fabrice Bellard formula -------------------------------------------- The algorithm used to check pi is based on Fabrice Bellard formula to compute directly 24 bits of pi at a given position n (for the details, see http://xavier.gourdon.free.fr/Constants/Algorithms/nthdigit.html) The 24 bits of pi at bit position n are also computed from the pi computation result (piresult) as follows : a) Compute x = 2^n * piresult b) Compute y the fractionnal part of x c) Compute the first 24 bits of y : y = 0.b_1b_2b_3... in base 2 The two sets of 24 bits are then compared. If they agree, the computation is right with a probability 1-2^(-24). ============ | Problems | ============ The program is not guaranteed free of bug. If some WARNING, ERROR or strange messages appear, you can report them to me (xavier.gourdon@free.fr) together with the PiFast.log file which should be generated (or at least the input values), so I can correct the program. Changing a little bit your input may make the program run correctly. ========================================= | What should be done for next versions | ========================================= * Reduce the disk memory used during the computation (for space problems but also for disk access timing) by compressing the disk saved data. * Compute other constants (log(2), gamma, for example). * Have a multithreaded version that run faster on multiprocessor machines * Have a windows interface. Email me your requests for next versions ! =========================== | Source code information | =========================== The PiFast source file is not available. Netherveless, I am planning to release it one day. PiFast has originally been written in C, most of it is now in C++ since version 3.3. I am using my own FFT and NTT code. ============== | Conclusion | ============== For any remarks on the program, huge computations experience, requests for next versions, email to xavier.gourdon@free.fr.