Algorithm for converting large hex numbers into decimal form (base 10 form)

Question

I have an array of bytes and length of that array. The goal is to output the string containing that number represented as base-10 number.

My array is little endian. It means that the first (arr[0]) byte is the least significant byte. This is an example:

#include <iostream>
using namespace std;

typedef unsigned char Byte;

int main(){
  int len = 5;
  Byte *arr = new Byte[5];
  int i = 0;

  arr[i++] = 0x12;
  arr[i++] = 0x34;
  arr[i++] = 0x56;
  arr[i++] = 0x78;
  arr[i++] = 0x9A;

  cout << hexToDec(arr, len) << endl;
}

The array consists of [0x12, 0x34, 0x56, 0x78, 0x9A]. The function hexToDec which I want to implement should return 663443878930 which is that number in decimal.

But, the problem is because my machine is 32-bit so it instead outputs 2018915346 (notice that this number is obtained from integer overflow). So, the problem is because I am using naive way (iterating over the array and multiplying it by 256 to the power of position in the array, then multiplying by the byte at that position and finally adding to the sum). This of course yields integer overflow.

I also tried with long long int, but at some point of course, integer overflow occurs.

The arrays I want to represent as decimal number can be very long (more that 1000 bytes) which definitelly requires a lot more clever algorithm than my naive one.

Question

What would be the good algorithm to achieve that? Also, another question I must ask is what is the optimal complexity of that algorithm? Can it be done in linear complexity O(n) where n is the length of the array? I really cannot think about a good idea. Implementation is not the problem, my lack of ideas is.

Advice or idea how to do that will be enough. But, if it is easier to explain using some code, feel free to write in C++.

Answer 1

You can and can not achieve this in O(n). All depends on the internal representation of your number.

1. For truly binary form (power of 2 base like 256)

   is this not solvable in O(n) The hex print of such number is in O(n) however and you can convert HEX string to decadic and back like this:

   • How to convert a gi-normous integer (in string format) to hex format?

   As creating hex string does not require bignum math. You just consequently print the array from MSW to LSW in HEX. This is O(n) but the conversion to DEC is not.

   To print bigint in decadic you need to continuously mod/div it by 10 obtaining digits from LSD to MSD until the subresult is zero. Then just print them in reverse order ... The division and modulus can be done at once as they are the same operation. So if your number has N decadic digits then you need N bigint divisions. Each bigint division can be done for example by binary division so we need log2(n) bit shifts and substraction which are all O(n) so the complexity of native bigint print is:

   O(N.n.log2(n))
   

   We can compute N from n by logarithms so for BYTEs:

   N = log10(base^n)
     = log10(2^(8.n))
     = log2(2^(8.n))/log2(10)
     = 8.n/log2(10)
     = 8.n*0.30102999
     = 2.40824.n
   

   So the complexity will be:

   O(2.40824.n.n.log2(n)) = O(n^2.log2(n))
   

   Which is insaine for really big numbers.

2. power of 10 base binary form

   To do this in O(n) you need to slightly change the base of your number. it will still be represented in binary form but the base will be power of 10.

   For example if your number will be represented by 16bit WORDs you can use highest base 10000 which still fits in it (max is 16536). Now you print in decadic easily just print consequently each word in you array from MSW to LSW.

   Example:

   lets have big number 1234567890 stored as BYTEs with base 100 where MSW goes first. So the number will be stored as follows

   BYTE x[] = { 12, 34, 56, 78, 90 }
   

   But as you can see while using BYTEs and base 100 we are wasting space as only 100*100/256=~39% is used from the full BYTE range. The operations on such numbers are slightly different then in raw binary form as we need to handle overflow/underflow and carry flag differently.

3. BCD (binary coded decimal)

   There is also another option which is to use BCD (binary coded decimal) it is almost the same as previous option but the base 10 is used for single digit of number... each nibel (4 bits) contains exactly one digit. Processors usually have instruction set for this number representation. The usage is like for binary encoded numbers but after each arithmetics operation is BCD recovery instruction called like DAA which uses Carry and Auxiliary Carry flags state to recover BCD encoding of the result. To print value in BCD in decadic you just print the value as HEX. Our number from previous example would be encoded in BCD like this:

   BYTE x[] = { 0x12, 0x34, 0x56, 0x78, 0x90 }
   

Off course both #2,#3 will make impossible the HEX print of your number in O(n).

Answer 2

The number you posted 0x9a78563412, as you have represented it in little endian format, can be converted to a proper uint64_t with the following code:

#include <iostream>
#include <stdint.h>

int main()
{
    uint64_t my_number = 0;
    const int base = 0x100; /* base 256 */
    uint8_t array[] = { 0x12, 0x34, 0x56, 0x78, 0x9a };

    /* go from right to left, as it is little endian */
    for (int i = sizeof array; i > 0;) {
        my_number *= base;
        my_number += array[--i];
    }
    std::cout << my_number << std::endl; /* conversion uses 10 base by default */
}

sample run gives:

$ num
663443878930

as we are in a base that is an exact power of 2, we can optimize the code by using

my_number <<= 8; /* left shift by 8 */
my_number |= array[--i]; /* bit or */

as these operations are simpler than integer multiplication and sum, it is expected some (but not much) efficiency improvement in doing that way. It should be more expressive to leave it as in the first example, as it more represents an arbitrary base conversion.

Answer 3

You'll need to brush up your elementary school skills and implement long division.

I think you'd be better off implementing the long division in base 16 (divide the number by 0x0A each iteration). Take the reminder of each division - these are your decimal digits (first one is the least significant digit).