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

-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:

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

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 .

**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.

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!

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?

**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 wrongAs expected, you added up more than ten to the 12th power terms so the first incorrect digit is in the 13th decimal place. However,