# Efficient algorithm for conversion of hexadecimal fraction to decimal fraction

Let's say I have some very long hex fraction like this:

What are some algorithms with an acceptable complexity to convert it to the associated decimal string:

0.246835...

?

• What do you mean by acceptable? Given that the decimal fraction can be repeating, do you want some (finite) level of precision or do you want some representation that specifies the repeating part exactly? Jul 12 '15 at 19:44
• @TomvanderZanden Any terminating hex fraction is a terminating decimal fraction, too, since 1/16=0.0625 is terminating. Jul 12 '15 at 23:19
• @DavidRicherby exactly. But moving into greater hex precision it starts to need a much greater amount of decimal precision very quickly... e.g. 0.0001 in hex = 0.00024414062 Jul 13 '15 at 2:05
• You haven't answered Tom's questions. What counts as acceptable complexity? Also, do you want the output printed to a specific level of precision, or do you want the algorithm to output the exact decimal string, down to the last digit? What have you tried? What's the best algorithm you came up with? What approaches have you considered? I'm worried we'll give you an answer but it won't be what you wanted.
– D.W.
Jul 13 '15 at 5:18
• @JosephNields Conversely, 0.1hex = 0.0625dec. That is, some fractions are much shorter in hex than decimal. Jul 13 '15 at 13:47

Suppose multiplication of two $n$-bit integers takes $M(n)$ time ($O(n\log n\log \log n)$ with Schönhage-Strassen).
Conversion between (general) bases can be done using divide and conquer. Given a hexadecimal integer $k<10^n$, recursively compute decimal representations of $\left \lfloor{\frac{k}{10^{\left \lfloor{n/2}\right \rfloor}}}\right \rfloor$ and $k\textrm{ mod }10^{\left \lfloor{n/2}\right \rfloor}$. The decimal representation of $k$ can then be found by concatenating the two recursively computed representations.
Since division and mod can both be done in $O(M(n))$ time, on an $n$-bit integer this algorithm has running time $T(n)=2T(n/2)+O(M(n))$. For Schönhage-Strassen multiplication, this evaluates to $O(n\log n\log n\log \log n)$.