4 ms·

Any chance we can see results for 10 digits as well? The reason I ask is I'm guessing that a lot of work will actually be with smaller numbers of digits. Is it

Any chance we can see results for 10 digits as well? The reason I ask is I'm guessing that a lot of work will actually be with smaller numbers of digits. Is it possible to design a math lib that uses native ints/floats for stuff that fits and switches in the big num stuff on overflow? I believe ruby does this, do any of the libs do it? I think the ruby approach is to cast the 32 bit items to 64 bit, do the operation into a 64 bit, see if any of the top 32 bits are set, if so, switch to bignum, if not, use the result. If tommath or any of the others do that, then I don't really care that much (for my purpose which is scripting langs that use tommath) about the big num perf. Faster is better but the high order bit for me, at least, is perf on the smaller numbers.

fdej 13y ago
Yes, for example the fmpz type in flint (http://flintlib.org/ http://flintlib.org/) implements this optimization, and also caches bignum objects for quick allocation/deallocation. Here is the benchmark with the mpir mpz type vs the flint fmpz type: mpz fmpz digits = 10: 4.24e-06 s 1.2e-06 s digits = 100: 1.28e-05 s 3.3e-06 s digits = 1000: 8e-05 s 2.7e-05 s digits = 10000: 0.001 s 0.0006 s digits = 100000: 0.017 s 0.013 s digits = 1000000: 0.25 s 0.23 s digits = 10000000: 4.32 s 4.08 s In fact, the benchmark is a bit biased against the mpz type because it spends a lot of time allocating and deallocating temporary mpz's. It would be much faster to replace the recursion by a loop with in-place operations when b - a < 20, say. (On the other hand, unoptimized code of this kind is probably quite common in practice...)