Problem
Give an algorithm that inputs an array of n base b1 digits representing a positive integer in base b1 and outputs an array of base b2 digits representing the same integer in base b2. Get as close as possible to linear time. Assume b1, b2 are fixed constants.
If we do the conversion digit-by-digit, the number of operations is really O(n2), since, for example, once we convert each digit we need to add up all the resulting O(n) bit numbers. We can do better using a divide-and-conquer algorithm using a FFT integer multiplication algorithm as a sub-routine. Assume n is a power of 2; otherwise, pad with 0's in the most significant digits.