I should make a blog post about this, but here are some thoughts.
The C code you started with is really poor quality, seemingly because it got involved with code golfing. Global variables, sigh -- that was ugly in the 1980s and still is. This makes it tough to follow and translate.
The rest of this is really all about performance. If you're happy using it, then great, the rest of this is just blathering on about details. But ever since as a kid I bought Petr Beckmann's book I've found this interesting. It was also one of my many digressions -- I needed a few million digits of Pi for a puzzle and was disappointed that the standard Perl modules were horribly slow, so went down the rat hole.
The spigot code you're using is one of the slower methods for generating N digits of Pi. There is a modified version of the simple C spigot from Winter, Flammenkamp, et al.) that runs about 8 times faster (code in ntheory, Luschny's Java version, many other variants on the web). I added a little bit to make sure it rounds correctly at reasonable sizes (the table maker's dilemma still applies, but not for quite some time). I actually only use it for <= 100 digits or if MPFR and GMP are not available, as those methods are far faster.
You can see a timing comparison of some C methods I measured in 2014 on RosettaCode. Spigot 1 in that table is Winter/Flammenkamp version (as mentioned, about 8x faster than the one you're using). Here is a (hastily assembled) chart of 13 algorithm/implementations I made today, all but one used from Perl. The time (in seconds) on the y-axis uses a log scale which lets us see how AGM and Chudnovsky have a favorably slope compared to the others (about 2.4x time per doubling of digits vs. 4x).
Pi timing graph
- y-cruncher is what you want if you really need a few billion digits for some project. It's pretty cool if you're interested in this stuff.
- Pari's Chudnovsky method (they call it Ramanujan + binary splitting) is definitely faster than AGM. This is basically the same method as Xue's Chudnovsky program shown on the GMP site, though implemented differently. That's the one method that was called using GP rather than plugged into Perl. Putting a GMP version of this in my module has been on my to-do list for a couple years.
- My AGM implementation in GMP (used in Math::Prime::Util aka ntheory when possible) is just a fraction slower than MPFR (I use the normal GMP mpf interface, they use MPFR of course). It's short code, quite fast, and asymptotically looks nice.
- The Machin formulas implemented in GMP are inferior to AGM or Chudnovsky at all sizes and get worse. Using updated formulas helps only slightly. They still easily beat the spigot methods and all but one of the Perl methods. Math::BigFloat used to use these (but in Perl not C+GMP).
- The spigot algorithms don't compete well for this task (producing N correctly rounded digits of Pi). There is no point in using GMP for these particular ones. Implementing it in Perl directly has a very large performance hit, as all these operations are really simple so C is going to shine.
- Math::BigFloat changed from Machin to AGM in version 1.999705 (2015). rt://90033 has some performance numbers. With the GMP back end it isn't bad. The overhead at small sizes isn't ideal. With the Pari or Calc back ends it's terribly slow (assuming you want 1000+ digits).
- I suspect if you used Math::GMPf or Math::AnyNum and wrote the simple AGM code it would be only a small penalty from the GMP code, so easily beat all the other Perl code shown. At that point you could just use the pi() function from Math::AnyNum which calls MPFR, or Pi() from ntheory which uses its best available choice from MPFR, GMP, C, or pure Perl.
Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
Read Where should I post X? if you're not absolutely sure you're posting in the right place.
Please read these before you post! —
Posts may use any of the Perl Monks Approved HTML tags:
- a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
| |
For: |
|
Use: |
| & | | & |
| < | | < |
| > | | > |
| [ | | [ |
| ] | | ] |
Link using PerlMonks shortcuts! What shortcuts can I use for linking?
See Writeup Formatting Tips and other pages linked from there for more info.
