[futqwish] Divide and Conquer Radix Conversion, attempt 2

Suppose we wish to convert the large hexadecimal number 0x1234567890ABCDEF to decimal.

Instead converting it directly into base 10, we first convert it to a two-"digit" number in base 1000000000 (10^9).  This base is chosen because, by calculating approximate logs, we know the answer will be about 10^18, so the base is half the number of decimal digits.

We calculate 10^9 in hexadecimal by repeated squaring.  Save the partial powers because we will need them later.  Divide the big number by 10^9 using your favorite subquadratic division algorithm, yielding a quotient and a remainder.  Note well this computation is done entirely in hexadecimal (in contrast to the previous attempt), yielding hexadecimal results.

Recursively apply the conversion to the quotient and remainder.

GNU MP uses a variation of this algorithm ("Binary to Radix").