1
$\begingroup$

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

0.3F30A21306AEFCBADE3230A593EFAEB395A39E

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

0.246835...

?

$\endgroup$
  • 3
    $\begingroup$ 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? $\endgroup$ – Tom van der Zanden Jul 12 '15 at 19:44
  • 2
    $\begingroup$ @TomvanderZanden Any terminating hex fraction is a terminating decimal fraction, too, since 1/16=0.0625 is terminating. $\endgroup$ – David Richerby Jul 12 '15 at 23:19
  • $\begingroup$ @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 $\endgroup$ – Joseph Nields Jul 13 '15 at 2:05
  • 2
    $\begingroup$ 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. $\endgroup$ – D.W. Jul 13 '15 at 5:18
  • $\begingroup$ @JosephNields Conversely, 0.1hex = 0.0625dec. That is, some fractions are much shorter in hex than decimal. $\endgroup$ – David Richerby Jul 13 '15 at 13:47
2
$\begingroup$

You can do better than quadratic in the length of the fraction, but doing so requires fast (subquadratic) multiplication algorithms such as Karatsuba or Schönhage-Strassen. First, multiply by a suitably large power of 10 to obtain an integer (note that the exponent of this power is at most linear in the length of the fraction). The problem is now to convert a hexadecimal integer to decimal.

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)$.

$\endgroup$
  • $\begingroup$ Schoenhage-Strassen works fine for huge numbers, but the overhead for the simple number in the question would be far too high. Even Karatsuba or one of the Toom-Cook algorithms would be far too much for such a simple number. A simple repeated div/mod 10 will do here. $\endgroup$ – Rudy Velthuis Jan 26 '17 at 11:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.