How can I convert a very large integer from one ba

Question

Are there known algorithms which will take a big integer with n digits encoded in one base/radix and convert it to another arbitrary base? (Let's say from base 7 to base 19.) n can be really big, like more than 100 000 digits, so I am looking for something better than O(n²) run time.

I have seen some algorithms that can multiply two huge integers using the Fast Fourier Transform (FFT), with the theoretical complexity of O(n log n), where n is the number of digits, so I wonder if something similar exists for bases/radix conversion?

Answer 1

I'm not well versed on the topic myself, but here's a page that hints at how to do radix conversion a bit faster than the naive remainder-and-divide algorithm:

• GNU MP - Binary to Radix

The page hints that you need a fast divide-and-conquer division algorithm, which in turn needs a fast multiplication algorithm (Karatsuba, Toom-Cook, FFT, etc.).