Fastest algorithm to convert hexadecimal numbers into decimal form without using a fixed length variable to store the result

Question

I want to write a program to convert hexadecimal numbers into their decimal forms without using a variable of fixed length to store the result because that would restrict the range of inputs that my program can work with.

Let's say I were to use a variable of type long long int to calculate, store and print the result. Doing so would limit the range of hexadecimal numbers that my program can handle to between 8000000000000001 and 7FFFFFFFFFFFFFFF. Anything outside this range would cause the variable to overflow.

I did write a program that calculates and stores the decimal result in a dynamically allocated string by performing carry and borrow operations but it runs much slower, even for numbers that are as big as 7FFFFFFFF!

Then I stumbled onto this site which could take numbers that are way outside the range of a 64 bit variable. I tried their converter with numbers much larger than 16^65 - 1 and still couldn't get it to overflow. It just kept on going and printing the result.

I figured that they must be using a much better algorithm for hex to decimal conversion, one that isn't limited to 64 bit values.

So far, Google's search results have only led me to algorithms that use some fixed-length variable for storing the result.

That's why I am here. I wanna know if such an algorithm exists and if it does, what is it?

Answer 1

Well, it sounds like you already did it when you wrote "a program that calculates and stores the decimal result in a dynamically allocated string by performing carry and borrow operations".

Converting from base 16 (hexadecimal) to base 10 means implementing multiplication and addition of numbers in a base 10^x representation. Then for each hex digit d, you calculate result = result*16 + d. When you're done you have the same number in a 10-based representation that is easy to write out as a decimal string.

There could be any number of reasons why your string-based method was slow. If you provide it, I'm sure someone could comment.

The most important trick for making it reasonably fast, though, is to pick the right base to convert to and from. I would probably do the multiplication and addition in base 10⁹, so that each digit will be as large as possible while still fitting into a 32-bit integer, and process 7 hex digits at a time, which is as many as I can while only multiplying by single digits.

For every 7 hex digts, I'd convert them to a number d, and then do result = result * ‭(16^7) + d.

Then I can get the 9 decimal digits for each resulting digit in base 10⁹.

This process is pretty easy, since you only have to multiply by single digits. I'm sure there are faster, more complicated ways that recursively break the number into equal-sized pieces.