libtom/libtommath — pull request #19 by BenGoldberg1 (2013-09-20 05:13:05+00:00)
Title: Speed up bn_map_toradix

Instead of repeatedly performing big number division by radix, we repeadly perform big number division by the largest power of radix which is <= MP_DIGIT_MAX.

Each remainder (which is an mp_digit) is repeatedly divided by radix, using ordinary integer division.

Since integer division is much faster than mp_div_d, this is a huge speedup.

When radix > sqrt(MP_DIGIT_MAX), the function should be the same speed as the original version.

I have not tested or benchmarked this code, but I know that the basic idea is sound.