Is there a way to convert a base 2^64 number to its base10 value in string form or display it in sta-CodePudding

Let's say I have a very large number represented using an array of unsigned long(int64), and I want to see its base10 form either stored in a string and/or display it to the standard out directly, how would I do that in C or C without using libraries like gmp or boost?, what algorithm or method should I know?

below is an example base2^64 number, with its base10 value in the comment

// base2^64
unsigned long big_num[3] = [77478, 656713, 872];

// base10 = 26364397224300470284329554475476558257587048

I don't exactly know if this is the correct way to convert another number base to base 10, but this is what I did:

To get the base10 value 26364397224300470284329554475476558257587048, I summed up all the digits of the base2^64 number that is multiplied to its base and raised by the index of the digit.

base10 = ((77478 * ((2^64)^2)) ((656713 * ((2^64)^1))) ((872 * ((2^64)^0)))) = 26364397224300470284329554475476558257587048

the only problem with this is that there is no primitive data type that can hold this super large sum...

I was just thinking if libraries like boost cpp_int and gmp represents their number like this, and if yes how do they convert it to it's base10 value in string form or display the base10 value in standard out?

Or do they just use half of the bits of the data types that they use like for example in unsigned long and maybe use something like base 10000?

CodePudding user response：

Repeatedly "mod 10" the array to find the next least significant decimal digit, then "divide by 10". Repeat as needed.

Avoid unsigned long to encode 64-bit values as it may be only 32-bit.

If code can encode the number not using the widest type and use uin32_t, then doing the repeated "mod 10" of the array is not so hard.

Below illustrative code still needs to reverse the string - something left for OP. Potential other warts too - hence the advantage of using big number libraries for this sort of thing.

#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>

// Form reverse decimal string
void convert(char dec[], size_t n, uint32_t b32[]) {
  // TBD code to handle 0

  while (n > 0 && b32[0] == 0) {
    b32  ;
    n--;
  }
  while (n > 0) {
    unsigned char rem = 0;
    // Divide by 10.
    for (size_t i = 0; i < n; i  ) {
      uint64_t sum = rem * (1ULL << 32)   b32[i];
      b32[i] = (uint32_t) (sum / 10u);
      rem = (unsigned char) (sum % 10u);
    }
    *dec   = (char) (rem   '0');
    if (b32[0] == 0) {
      b32  ;
      n--;
    }
  }
  *dec = 0;
}

Sample

int main() {
  // unsigned long big_num[3] = [77478, 656713, 872];
  uint32_t big_num[6] = {0, 77478, 0, 656713, 0, 872};
  size_t n = sizeof big_num / sizeof big_num[0];
  char s[sizeof big_num * 10   1];
  convert(s, n, big_num);
  printf("<%s>\n", s);
  // <84078575285567457445592348207400342279346362>
  //  26364397224300470284329554475476558257587048
}

CodePudding user response：

To get the decimal representation of this number, you need to repeatedly divide the number by 10 and take the remainder to get the decimal digits. This means you need to implement long division for big numbers, which also requires implementing long addition, subtraction, and multiplication.

That's a lot of code that big number libraries give you, so just use one.