An Authentic Archive of Arithmetic
Automata that
Ascertain Archimedes' vAlue
(Annoying Alliteration, Ay?)
"Other people talk a lot about the
areas of circles, but I'm actually
doing something about them"
-Dilbert
This page is dedicated to the almighty computer; more specifically to computer programs that take the mystery and magic out of the number pi. To a certain extent they all do the same thing- chew up enormous time and resources for something silly- but you'll be able to see a variety of programming styles and levels of efficiency, both from authors and algorithms (alliteration again!). You'll also see the wonderful battle between massive low-level optimization and clever algorithms, and the amazing results that ensue when both work together.
Folks who visit regularly know by now that this page hasn't really changed in a godawful long time (more than a year). That's because my time has been totally consumed by my job, and it doesn't look like that will change for the forseeable future (i.e. at least a week). Thus, it is with great regret that I declare the content at this URL to be permanent and frozen.
Don't worry though! In the last 15 months the Web has lit up with people who stockpile pi calculators, and are more enthusiastic and organized by far than I've been. I like to think that I'm solely responsible for getting Carey, Dara, and Stu into distributing pi source on the Web, but that's overstating my importance and I know it. Nonetheless, all of them actively collect and test pi crunchers, and if you have one that they don't, please tell them and not me; otherwise, you may end up like Mr. Henry below.
Think calculating pi is hard? Never fear, the religious right has made it easy. I've since found out the story was a clever hoax (Guy Hunt was governor of Alabama until 1993) but I was taken hook line and sinker.
In 1991 The New Yorker Magazine published a wonderful article on the Chudnovsky brothers, Daniel and Gregory. The article also included lots of stuff about pi. Finally, a few months ago somebody scanned and posted the article, and I hope it gives you as much enjoyment as it gave me. Note that this is not intended to be a violation of copyright.
If you want to find out how one makes a pi-cruncher, there are several sources that can help you. An excellent introduction is by Carey Bloodworth, who has written a general treatise and a primer on arctangents. I've written an introduction to high-precision arthmetic for Basic, as has Bruce Dawson for C++. Carey's latest calculator (available on his page) also has extensive tutorials on high-precision and high-performance integer arithmetic.
The Basics
Here can be found the shrimps, computer programs that can
compute pi out to a few thousand digits quickly. They're available in
profusion, so I've had to be picky in choosing cool ones. All are
characterized by requiring "n squared time", i.e. doubling the number of
digits you want multiplies the time needed by four. All of these
programs except one compute pi by adding up arctangent series, and even
that one is derived from an arctangent formula.
pi8.c , a program by
Carey Bloodworth, is a wonderful introduction to multiprecision
arithmetic, and is very clearly written and versatile. It can work in
integer or floating point math and lets you choose one of 5 or 6
arctangent formulas to work with. It's capable of millions of digits of
pi; the only drawback is that it's somewhat generic (and thus somewhat
slow...see the timing results in the source code).
Much smaller (but much wimpier) is tinypi.com, an
adorable little program in 8086 assembly. Actually it's uuencoded and
stuck into a detailed explanation of what it does, so you'll need a
uudecoder to actually get at the program. On my 486 computer it'll
get 9304 digits of pi in just under two minutes. The chances are
overwhelming that it uses Euler's formula, both for simplicity and because
of the number 14 in the code (exercise: What's so all-fired
important about the number 14?!).
Tinypi has gotten a lot of admiration from assembly programmers. If
you want the ultimate in ultra-small pi programs, Mark Andreas has gotten
tinypi's 125 bytes down to an even smaller 113. He's also crunched out
another version that outputs in hex, is only 112 bytes, is 30% faster, and
produces about 30% more digits (if you converted from hex). Here's a
summary of our correspondence, and a bunch of
improved versions of Tinypi. Is 112 bytes the
limit? No way! Here's a 93 byte Tinypi, and
an 80 byte Tinypi, both with assembly source.
Henrik Pedersen has gotten the decimal version of Tinypi down
to an eensy 93 bytes. Look!
NEW! (Actually, inexcusably old) In late July 1999, Glenn Henry
sent me another decimal pi calculator,
even smaller (86 bytes) than Henrik's offering above. Glenn
is the CEO/President of Centaur Technology Inc, the company that
brought you the WinChip x86 processor; it's a testament to how
stressful competition in the processor business is when you turn to
low-level x86 programming just to relax! Anyway, profound apologies
for not taking the time out to add this gem to the public pi record.
I dimly remember Centaur getting bought by IDT a while ago (or doing the
buying, I don't remember). Mr Henry may not even be there anymore!
NEW! The tiny pi calculators just keep pouring in. Henrik
Pedersen strikes again with a 77 byte
calculator.
NEW! Gjerrit Meinsma sent in a a tiny C program.
NEW! Bertram Felgenhauer has smashed the previous tiny calculator record
with a different algorithm coded up in 52 bytes!
Here is the code from his web page.
NEW! "Baz" sent me this calculator by Alan
Pittman, which uses Machin' formula. It's old and slow, but the user interface
and coding style are really nice.
At last, something of my own: this is the final
version of my first C program (did I ever mention that I learned C to
compute pi faster? Only afterwards did I realize you can do other things
with it...), a highly optimized cruncher that adds up Klingenstierna's
arctangent formula for pi. It's much faster than most programs in this
league (it averages five times as fast, 4.73 seconds for 5000 digits on
my old 486), and is also capable of about 200,000 digits of pi. Integer
math is used exclusively, so it would likely be too slow on more
modern computers.
If compiling on a Sparc, make sure to specify the v8 or better instructions;
these include hardware multiplies and divides that speed the program up
by a factor of five!
If you have a Pentium (or a Sun or Alpha or whatever) you may want to take
a look at a similar version
that uses floating point math a lot (it uses Machin's formula). It's
30% faster on a Pentium than the integer version, and seven or eight times
faster on a Sun! NOTE: very careful tests showed that originally errors
crept into the calculated results. The floating point version here works
correctly and is also very slightly faster. I used to think this was the
best you could do to calculate pi using series without resorting to
hand-coded assembly language, but I was spectacularly wrong, as you'll
soon see.
If you hate C, there's also a similarly optimized version
in QuickBasic that uses Machin's formula
(a little faster than Klingenstierna's for this language). It's much
slower, needing 28.5 seconds for 5000 digits even when compiled.
NEW! (Actually very old) I just realized that
this Machin calculator
was floating around my archives, written by Landon Rabern. Haven't
actually tried it, but it's supposed to be a tad faster than pi_c50
above.
Then there's Terje Mathisen, expert assembly programmer and really nice
guy. He dashed off this program in a few
hours (mine took a whole Christmas break), and it adds up Machin's
formula in less than half the time my program needs (2.1 seconds for 5000
digits on my poor 486). He uses several tricks that include combining
terms, and doing one divide and two multiplies instead of two divides. I
shudder to think what he can do with floating point math.
Now for the heavy artillery, a monster written
by Dario Alpern in tremendously optimized 80386 assembly. The final
product is quite small, but is very versatile (output in several formats,
and also capable of calculating ln 2), and awesomely fast (just
over one second for 5000 digits on my computer, three times as fast as my
effort). It can reportedly calculate a million digits of pi in just under
a day on a Pentium 90! Unfortunately, all the documentation is in Spanish,
and I would be eternally grateful if somebody could translate it for me.
Likewise, I changed the program's name from "pi" to "pialpern" to
distinguish it from the other programs here. Note that
his web page contains
another version that uses DPMI and is almost twice as fast.
Ask, and you shall receive... Jan Kraak translated the dpmi routines
in Dario Alpern's pi program and coded up Machin's formula using them.
The result is only 30% faster than my program
above, but at least I can read it.
For those of you who like the original monster calculator more, Dario
has kindly translated the comments to english.
Here's the DPMI version. If you're sick of pi by this point, it can
also calculate e and ln2, in any base from 2 to 36. This program
started out as a teaching aid, but has just grown and grown.
Alpern's program was the king of the hill for raw speed, but that's
changed recently. Yours truly has written something
faster, a series adder-upper that absolutely flies. For comparison,
here's how long 50,000 digits takes on a Pentium 200MMX:
Note that pi_c51f.c is itself an average of five times faster than the
other pi programs not listed. On a modern processor blokpi is a
rocket! It also uses a funky formula instead of an arctangent, includes
inline assembly code for DJGPP, and is configurable for any machine with
an ANSI C compiler and any formula (possibly for some other constant) that
has a similar form. I've also banged out a detailed description of
how it works and how to configure it. Note that
blokpi will only run way fast on a Pentium or better, or a RISC machine.
It boggles the mind: Daniel Shanks' computation of 100,000 digits in
1967(?) took almost nine hours, and 100,000 digits with this program
(which also adds up a series) takes a minute and a half on my machine.
Want to make your own arctangent adder-upper, but can't find an arctangent
formula to use that's uniquely "you"? Don't worry, you need only visit one
place to find
all of them
.
pi_c51f.c: 82 sec
pi32: 40 sec
pialpern (XMS): 65 sec
pialpern (DPMI): 36 sec
blokpi (no asm): 27 sec
blokpi (asm): 22 sec
blokpi on an UltraSPARC-1 (no asm, Sun C compiler): 14.4 sec
Bigger Fish
So much for introductions. If you have a hankering for
millions of digits of pi, you should really take a look here. These
programs are not basic, in that understanding why they work
requires knowledge of elliptic integrals and modular functions. All of
these programs compute pi using an iteration, which requires square
roots, reciprocals, and multiplication of enormous size numbers. Contrast
this to all of the previous programs which really only needed basic
arithmetic on numbers ten digits long or less. You probably can't do
any better asymptotically: these guys can do in minutes what would take
days or even weeks for the Shrimps.
In practice, the major bottleneck of a Bigger Fish program is how fast one
can multiply large numbers together; all the other stuff can be turned
into multiplies and additions (adding is easy, even at the million-digit
level). Ultimately, for raw terrifying speed you must use the Fast
Fourier Transform, and know both the algorithms and your hardware inside
and out.
Carey Bloodworth and I both used to have programs here to start
things off, which programs are not here anymore. In Carey's case, pi_agm.c
was never meant to see the light of day, and somehow wound up in Bob
Stout's C Snippets collection (where I found it). It was well written
and easy to follow, and even moderately fast; but ultimately it was
supposed to be kept in a cellar somewhere while its author went on to
better things. Besides, Carey has several other offerings here
which are much more interesting.
My case is slightly different. Though I remember fondly the two weeks
it took to write mine, and the terrible concentration required, having
my program up here has become painful to me. It ended up so clumsy, and
so slow, and I know so much more now, that I don't like even to look at
it. To think that I was so proud of having finished it...well, I'm
drinking milk, and one day may produce something worthy of being included
here, among the digit-hunting elite.
I also used to have a million digits of pi at this point, but I got rid
of the pile for several reasons. You can get billions of
digits elsewhere, but more importantly the programs that follow are
so fast that you can compute a million digits yourself in much less
time than it would have taken to download them!
If you think this FFT stuff is neat, or think that no one can be nuttier
than me about pi, you really should look
here. Joerg Arndt's obsession
with pi dwarfs mine, and his page contains piles of information about all
manner of things computational.
Colin Percival has used Bellard's formula and a grass-roots
distributed computing scheme to get the five trillionth hex digit of pi.
This link will point you in the right
direction; he's presently in the middle of a much larger calculation.
It's a bird! It's a plane! It's Super Pi!! Able
to crunch tall numbers in a single bound, Super Pi is a Windows program by the
people at the U of Tokyo, the same people that recently calculated pi to 192
billion digits (a small indication that they know what they're doing).
Super Pi needs less than fifteen minutes to calculate a million (2^20)
digits of pi on my Pentium, and is capable of over 32 million digits
precision.
Super Pi was the fastest cruncher in the west for a long time, but it's
rather an old program, and other efforts have happened since.
Mikko Tommila and his apfloat
large integer package, for example. It turns out that the sample
pi calculator he wrote to show off the package beats Super Pi by a nose.
However, I'm told that the newest version of apfloat (v1.5) isn't quite
as fast for digit hunting.
NOTE: Carey has told me that the 486 version fails an assertion at half a
million digits, and the 486 assembly code may have a bug in it somewhere.
I'm told that the latest version of apfloat includes a much faster pi
calculator.
There's also the large-integer package written
by Takura Ooura that uses floating point FFTs.
The code contains radix 2, 4, and 8 FFTs and can also do real
transforms and sine/cosine transforms. Remarkably, on a fast processor
the sample pi calculator written to test the package can keep up
with Carey's floating point monster. It even comes with Fortran versions
of the same routines, and includes a nice basic suite of large-integer
stuff. On my Pentium it needs just 88 seconds for a quarter million digits
of pi, almost an order of magnitude faster than Fabrice's Big Fish.
Ooura has apparently been tuning his library constantly; you'd better
pass by one of the other pi collections I mentioned to get the latest
version.
Carey Bloodworth has been cranking out pi calculators faster than I could
have imagined. His last three are already obsolete!
Here's version 2.1, an extension of his disk-based number-theoretic approach to high-speed multiplication of very large numbers;
it's been extensively reorganized and is even faster than version 2.0; for
purists it also includes several of his older programs. It also includes a much nicer user interface than before. Don't miss out on the latest in monster
digit-hunting!
You'll find exhaustive documentation and a range of options to tweak for
your particular system. Unfortunately, using number theory in programs
like this requires assembly language for maximum speed. You can go generic
(there seem to be three versions of everything in here), or if you have
the DJGPP compiler you can use some hand-hacked assembly I wrote to
improve performance on later x86 machines. For the assembly-code speed
freaks out there, the Fourier routines are
available separately.
Only a short while after version 2.1 was released, we now have
version 2.2, which has cleaner config files,
souped-up memory allocation code for DOS, and much better integration
of the Pentium code into the Fourier routines. On my Pentium
this version is more than twice as fast as version 2.0!
Man Lee has used version 2.2 to compute over 256 million digits of
pi in just over three days on his 400MHz Pentium II. This is by far the
largest number of digits computed on a machine of this size!
NEW! Oh man, that last snippet was so outdated. Carey's program
is now up to version 2.31 and he's still working on it. This version
has actually computed a billion digits of pi (here's
a short version of the original announcement; a more complete version
is probably in DejaNews somewhere).
NEW! Out of the blue one day, Xavier Gourdon announced another pi calculator,
one that was faster than any other for desktop use. For the last year or so
it's consistently won every speed race and has been used to compute awesome
amounts of pi digits. First 2 billion, then 6 billion, and just recently
over 8 billion digits of pi! For years you needed a supercomputer to do
anywhere near that much, but not anymore! Also, unlike every other program
in this league, Xavier's calculator doesn't use the Gauss-Salamin formula;
instead he uses binary splitting and massive large-integer multiplies to
accelerate the summation of infinite series (he uses two, one by the
Chudnovskys and a backup series by Ramanujan to check the calculations).
Xavier's page will explain more.
Can you do better?
You: Okay, okay, enough with the sob story!
Gimme the loot, I can take it!
It seems that Fabrice Bellard is a digit-hunting heavyweight, as
his offering shows. It turns out that FFT
multiplication can be done using integer math as well as floating point,
and this program shows how. I also really like the coding style.
You: What the hell was that?! That thing was huge!
You never said anything about all the comments
being in French, and I don't know number theory!
Me: Shut up! Did you think this would be easy? Not every-
one can pull off a program like this, it takes a lot
of skill and a lot of math. You can't just read "FFTs
for Dummies" and dash off a Gauss-Salamin calculator.
You: well, I'm not impressed. I asked for 9000 digits and
Bellard's "super" program took over 10 seconds to
finish. Your blokpi can do the same thing in less than
one second on the same machine.
Me: Bellard's program is the slowest and simplest of the Big
Fish here, and blokpi is the fastest Shrimp. And you're
not thinking big enough: for 270,000 digits blokpi needs
about 10 minutes, and Fabrice's gem needs 13. They're
almost even. Now double the digits: blokpi now needs 40
minutes, pibelard needs maybe 30. And it gets worse with
the other programs here: for the fastest, the crossover
point is less than 32,000 digits!
Weirdos
There's plenty of room in pi to be weird, and there are some
programs out there that are pi-related but otherwise beyond
classification. They go here; unfortunately, it seems I'm going to have to
make all of them. This section will hopefully expand...someday.
Gregory's series, namely pi = 4 - 4/3 + 4/5 - 4/7 + 4/9 -..., has been
called one of the neatest in all of math. If you're like me, you sometimes
wonder what the first five trillion terms of this series add up to; of
course, if you're like me you need some serious help. However, for those
of you like me, this program can do the job.
Written in QuickBasic, it'll add up an enormous number of terms of
Gregory's series, and doesn't need the age of the universe to do so.
Why is it interesting? Take a look at the sum of 5,000,000,000,000 terms:
3.14159265358959323846264338327950288419916939937510582097494459220...
^ ^ ^
wrong wrong wrong
As expected, you added up more than ten to the 12th power terms so the
first incorrect digit is in the 13th decimal place. However, the
next 26 digits are all correct! Then you get one wrong digit and
then 26 more correct ones! *I* think that's pretty interesting.
Incidentally, the calculation took about .16 seconds on my 486; for more
info on the weird results, go hunt up a paper by Borwein, Borwein and
Dilcher in the American Mathematical Monthly of October 1989 called
"Pi, Euler Numbers, and Asymptotic Expansions".