|Pathologically Eclectic Rubbish Lister
Re: porting C code to Perlby danaj (Friar)
|on Oct 25, 2017 at 02:02 UTC
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).