Yes, for example the fmpz type in flint (http://flintlib.org/ http://flintlib.org/) implements this optimization, and also caches bignum objects for quick alloc

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