ec2a96b0ad
Considering ways to take the algorithm and turn it into OpenCL/Boost::Compute functions/code which would offer a large speed increase. Also, if I can figure out how to start from any arbitrary digit (which is supposed to be possible) then multi-threading would also give great speedups. |
||
|---|---|---|
| .depend | ||
| .gitignore | ||
| LICENSE | ||
| Makefile | ||
| Makefile.win | ||
| README.md | ||
| Spigot.cpp | ||
| Spigot.hpp | ||
| main.cpp | ||
README.md
Pi Spigot in C++
What is spigot?
Spigot is an algorithm that calculates digits of pi. Each time you "pump" the spigot, you will get some number of digits out. Depending on the internal state of the algorithm, you might get no digits, 1 digit (most of the time), or 2+ digits. So in order to get x number of digits, you pump the spigot x number of times, and you should generally get that many digits out. The algorithm uses a vector of ints, sized to n * 10/3 where n is the number of requested digits. So for 10000 digits out, the vector will be 33333 digits long. This is to ensure there are enough digits to maintain precision.
Spigot is very fast for small values of n, but as n gets bigger, it slows down considerably. For example, calculating a million digits took about 18 hours, but 50 million digits had only produced just over 50k digits in that same amount of time. This is because the vector gets so much longer -- compare 3.3 million versus 166 million -- and each "pump" of the spigot requires accessing every single digit of the vector from n to the end. Because of this, spigot also speeds up as it gets closer to reaching its target, meaning predicting how long it will take to complete is non-obvious.
Why Spigot?
The Chudnovsky algorithm is much more efficient, although also more complicated to implement. The Spigot algorithm does scale infinitely, and is simple to implement, so for calculating digits of Pi it used to be a great choice. But now that tools like y-cruncher exist which can calculate literally trillions of digits in the span of weeks on supercomputers exist, spigot is not used much anymore. But I think it's a cool algorithm, as it uses integers and integer division to calculate a transcendental number! It's also a good algorithm to practice a new language with. There are quite a few little gotchas that differ from language to language, and implementing an algorithm like spigot is a good way to learn common mistakes in a language. I have written this version in C++, and before this I also wrote a version in Python. The speedup from moving to C++ is simply astounding, and with gcc using full optimization, the algorithm can rip through even many tens of thousands of digits very quickly.