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.