C: print a BigInteger in base 10

Question

I am using this struct to represent 128bit integers:

typedef struct {
    uint64_t low, high;
} uint128;

(Unless you can point me to a fast 128bit integer library I can not change that)

Now I want to print such a value in base 10, using printf. I probably need division by 10 to do that, but no division is implemented yet.

How can I do this? The solution does not have to be super efficient, as long as it works.

EDIT: I like all solutions you came up with. You are awesome.

Answer 1

If you don't want to implement division for 128bit value, you could precompute several (~40) 128 bit values that represents powers of 10, and use substraction.

Actually only higher qword have be processed in this way, because for lower part you can use printf("%I64d").

EDIT: here is an example (it will print a short using only arithmetics on char):

unsigned char pow10[][2] = {
    {0,   1},   // 1
    {0,  10},   // 10
    {0, 100},   // 100
    {3, 0xE8},  // 1k
    {0x27, 0x10}};  // 10k == 0x2710

#define HIGH 0
#define LOW  1

void print_dec(unsigned char H, unsigned char L){
    unsigned char L1;
    int pwr = 4, ctr = 0;
    while (pwr >= 0){
        int c = pow10[pwr][LOW] > L;
        L1 = L - pow10[pwr][LOW];
        if (H >= pow10[pwr][HIGH] + c){     
            H -= pow10[pwr][HIGH] + c;
            L = L1;
            ctr++;
        } else {
            printf("%d", ctr);
            ctr = 0;
            pwr--;
            //here we could add a check for H to be 0, so that we could use
            //printf() for lower half. we just have to be careful with 
            //leading zeroes in L, the simpliest way is to use printf("%03d",L)
        };
    };
    printf("\n");
};

int main(){
    unsigned short n = 12345;
    printf("%d should be ", n);
    print_dec((n >> 8) & 0xFF, n & 0xFF);
    return 0;
};

You can use smaller number of precomputed powers of 10, but it will make it slower (ex, having them in steps of 100 will make ctr to be in range 0..99.

Answer 2

void printu128(uint128 n) {
  int d[39] = {0}, i, j;
  for (i = 63; i > -1; i--) {
    if ((n.high >> i) & 1) d[0]++;
    for (j = 0; j < 39; j++) d[j] *= 2;
    for (j = 0; j < 38; j++) d[j+1] += d[j]/10, d[j] %= 10;
  }
  for (i = 63; i > -1; i--) {
    if ((n.low >> i) & 1) d[0]++;
    if (i > 0) for (j = 0; j < 39; j++) d[j] *= 2;
    for (j = 0; j < 38; j++) d[j+1] += d[j]/10, d[j] %= 10;
  }
  for (i = 38; i > 0; i--) if (d[i] > 0) break;
  for (; i > -1; i--) putchar('0'+d[i]);
}

Answer 3

Assuming you've already implemented functions to perform math on uint128, you could break the number up into 3 parts and use the built-in 64-bit printing capabilities of printf. Since the largest 64-bit number is 20 digits long, that means all 19-digit decimal numbers can be printed that way, but since the largest 128-bit number is 39 digits long, we can't break it up into only 2 parts, since there's a chance that we might end up with a 20 digit number bigger than the largest 64-bit number.

Here's one way to do it, dividing first by 10²⁰ to get a quotient no larger than 3,402,823,669,209,384,634. We then divide the remainder (itself no larger than 10²⁰) by 10¹⁰ to get another quotient and remainder each less than 10²⁰, which both fit in a 64-bit integer.

void print_uint128(uint128 value)
{
    // First power of 10 larger than 2^64
    static const uint128 tenToThe20 = {7766279631452241920ull, 5ull};
    static const uint128 tenToThe10 = {10000000000ull, 0ull};

    // Do a 128-bit division; assume we have functions to divide, multiply, and
    // subtract 128-bit numbers
    uint128 quotient1 = div128(value, tenToThe20);
    uint128 remainder1 = sub128(value, mul128(quotient, tenToThe20));
    uint128 quotient2 = div128(remainder1, tenToThe10);
    uint128 remainder2 = sub128(remainder1, mul128(remainder1, tenToThe10));

    // Now print out theresult in 3 parts, being careful not to print
    // unnecessary leading 0's
    if(quotient1.low != 0)
        printf("%llu%010llu%010llu", quotient1.low, quotient2.low, remainder2.low);
    else if(quotient2.low != 0)
        printf("%llu%010llu", quotient2.low, remainder2.low);
    else
        printf("%llu", remainder2.low);
}

Answer 4

You may use multiplication to print a number.

1. As 2¹²⁸ is about 340E36, first determine leading digit, by comparing number with 100E36, 200E36 and 300E36 boundaries. Write a digit and subtract nearest lesser boundary. E. g. If number is 234.6776E36 then nearest lesser bounary is 200E36, digit is '2' and after subtraction you should get 34.6776E36.

2. Now get next digit using comparison with numbers 10E36...90E36. Of course it is 128 bit comparison. Write a digit and subtract hearest lesser boundary as above. (For 34.6776E36 from above digit is '3', boundary is 30E36 and remainder is 4.6776E36)

3. Then multiply number by 10 and repeat from stage 2, total 38 times to print each digit. (4.6776E36 -> 46.776E36...)

UPD: Added subtraction I missed first. And examples.

UPD2: The need of dedicated step for 1-st digit is jus because if you multiply the number next to it you should get an overflow, if remainder is greater than 34E36.