18

I'm trying to convert a 128-bit unsigned integer stored as an array of 4 unsigned ints to the decimal string representation in C:

unsigned int src[] = { 0x12345678, 0x90abcdef, 0xfedcba90, 0x8765421 };
printf("%s", some_func(src)); // gives "53072739890371098123344"

(The input and output examples above are completely fictional; I have no idea what that input would produce.)

If I was going to hex, binary or octal, this would be a simple matter of masks and bit shifts to peel of the least significant characters. However, it seems to me that I need to do base-10 division. Unfortunately, I can't remember how to do that across multiple ints, and the system I'm using doesn't support data types larger than 32-bits, so using a 128-bit type is not possible. Using a different language is also out, and I'd rather avoid a big number library just for this one operation.

Improve this question
10
  • If you don't want a bignum library you are going to have to implement the long division yourself. It works like the pen-and-paper algorithm, only easier because it's binary so you don't have to make so many guesses. You will find that you need subtraction and shift. Are you sure you don't want to use a bignum library? You are going to implement a rather complete one yourself. Commented Nov 5, 2011 at 21:32
  • 4
    Decimal is for humans. They tend to lose interest after the 7th digit. What exactly is the point of this? Commented Nov 5, 2011 at 21:35
  • How should the above be printed out? As "0x1234567890abcdef..."? As decimal? Commented Nov 5, 2011 at 21:35
  • 1
    @ephemient "(The input and output examples above are completely fictional; I have no idea what that input would produce.)" He doesn't know xD Commented Nov 5, 2011 at 21:38
  • 4
    You could use the double dabble. Commented Nov 5, 2011 at 21:39

8 Answers 8

Reset to default
11

Division is not necessary:

#include <string.h>
#include <stdio.h>

typedef unsigned long uint32;

/* N[0] - contains least significant bits, N[3] - most significant */
char* Bin128ToDec(const uint32 N[4])
{
  // log10(x) = log2(x) / log2(10) ~= log2(x) / 3.322
  static char s[128 / 3 + 1 + 1];
  uint32 n[4];
  char* p = s;
  int i;

  memset(s, '0', sizeof(s) - 1);
  s[sizeof(s) - 1] = '\0';

  memcpy(n, N, sizeof(n));

  for (i = 0; i < 128; i++)
  {
    int j, carry;

    carry = (n[3] >= 0x80000000);
    // Shift n[] left, doubling it
    n[3] = ((n[3] << 1) & 0xFFFFFFFF) + (n[2] >= 0x80000000);
    n[2] = ((n[2] << 1) & 0xFFFFFFFF) + (n[1] >= 0x80000000);
    n[1] = ((n[1] << 1) & 0xFFFFFFFF) + (n[0] >= 0x80000000);
    n[0] = ((n[0] << 1) & 0xFFFFFFFF);

    // Add s[] to itself in decimal, doubling it
    for (j = sizeof(s) - 2; j >= 0; j--)
    {
      s[j] += s[j] - '0' + carry;

      carry = (s[j] > '9');

      if (carry)
      {
        s[j] -= 10;
      }
    }
  }

  while ((p[0] == '0') && (p < &s[sizeof(s) - 2]))
  {
    p++;
  }

  return p;
}

int main(void)
{
  static const uint32 testData[][4] =
  {
    { 0, 0, 0, 0 },
    { 1048576, 0, 0, 0 },
    { 0xFFFFFFFF, 0, 0, 0 },
    { 0, 1, 0, 0 },
    { 0x12345678, 0x90abcdef, 0xfedcba90, 0x8765421 }
  };
  printf("%s\n", Bin128ToDec(testData[0]));
  printf("%s\n", Bin128ToDec(testData[1]));
  printf("%s\n", Bin128ToDec(testData[2]));
  printf("%s\n", Bin128ToDec(testData[3]));
  printf("%s\n", Bin128ToDec(testData[4]));
  return 0;
}

Output:

0
1048576
4294967295
4294967296
11248221411398543556294285637029484152
Improve this answer
Sign up to request clarification or add additional context in comments.

11 Comments

unsigned long is 8-byes on a 64-bit system. I see that you mask the values of n while shifting and use sizeof, which is great, but generally if you call something uint32, it should be 4-bytes long. I'd suggest changing the typedef to unsigned int, or using long long and changing the typedef to uint64 (or just using stdint.h).
I like this -- all fast operations, the only disadvantage I can see is that it's O(n^2) to the number of bits. Why the "& 0xFFFFFFFF"? Wonder about changing the "s[j] += s[j] - '0' + carry;" to "s[j] = (s[j] << 1) | carry;" and then doing a pass over the string at the end with "s[j] += '0';
@BobbyPowers: unsigned int is not guaranteed to be at least 32-bit long. unsigned long is. Whether the system is 64-bit or not is irrelevant and beyond the C standard.
@6502: I didn't claim it would be fast(er|st). It's just a way to do the task w/o division and without many precalculated powers of 10.
Rather than defining your own uint32, use standard uint32_t from stdint.h instead.
|
7

Straightforward division base 2^32, prints decimal digits in reverse order, uses 64-bit arithmetic, complexity O(n) where n is the number of decimal digits in the representation:

#include <stdio.h>

unsigned int a [] = { 0x12345678, 0x12345678, 0x12345678, 0x12345678 };

/* 24197857161011715162171839636988778104 */

int
main ()
{
  unsigned long long d, r;

  do
    {
      r = a [0];

      d = r / 10;
      r = ((r - d * 10) << 32) + a [1];
      a [0] = d;

      d = r / 10;
      r = ((r - d * 10) << 32) + a [2];
      a [1] = d;

      d = r / 10;
      r = ((r - d * 10) << 32) + a [3];
      a [2] = d;

      d = r / 10;
      r = r - d * 10;
      a [3] = d;

      printf ("%d\n", (unsigned int) r);
    }
  while (a[0] || a[1] || a[2] || a[3]);

  return 0;
}

EDIT: Corrected the loop so it displays a 0 if the array a contains only zeros. Also, the array is read left to right, a[0] is most-significant, a[3] is least significant digits.

Improve this answer

6 Comments

It won't print anything if a[0]=a[1]=a[2]=a[3]=0.
@Alex, yes, I know. Should be do {} while();
Unfortunately, uses 64-bit arithmetic, which isn't available. ... although I guess I could recast the problem as 8 16-bit values, and which would allow me to use 32-bit arithmetic where you use 64, but would require double the number of operations.
@Silverhalide: what kind of ancient C compiler are you using? (AFAIK the last C++ standard from 2003 didn't have long long, but the current C standard from 1999 has it, can it be that you're compiling the code as C++?).
@Silverhalide, no problem, it's trivial to convert it to use only 32-bit or even only 16-bit arithmetic, just the array elements would be 16-bit or 8-bit, respectively, and the array will contain 8 or 16 elements. I will add a version with only 32-bit arithmetic in a minute.
|
3

A slow but simple approach is to just printing digits from most significant to least significant using subtraction. Basically you need a function for checking if x >= y and another for computing x -= y when that is the case. Then you can start counting how many times you can subtract 10^38 (and this will be most significant digit), then how many times you can subtract 10^37 ... down to how many times you can subtract 1.

The following is a full implementation of this approach:

#include <stdio.h>

typedef unsigned ui128[4];

int ge128(ui128 a, ui128 b)
{
    int i = 3;
    while (i >= 0 && a[i] == b[i])
        --i;
    return i < 0 ? 1 : a[i] >= b[i];
}

void sub128(ui128 a, ui128 b)
{
    int i = 0;
    int borrow = 0;
    while (i < 4)
    {
        int next_borrow = (borrow && a[i] <= b[i]) || (!borrow && a[i] < b[i]);
        a[i] -= b[i] + borrow;
        borrow = next_borrow;
        i += 1;
    }
}

ui128 deci128[] = {{1u,0u,0u,0u},
                   {10u,0u,0u,0u},
                   {100u,0u,0u,0u},
                   {1000u,0u,0u,0u},
                   {10000u,0u,0u,0u},
                   {100000u,0u,0u,0u},
                   {1000000u,0u,0u,0u},
                   {10000000u,0u,0u,0u},
                   {100000000u,0u,0u,0u},
                   {1000000000u,0u,0u,0u},
                   {1410065408u,2u,0u,0u},
                   {1215752192u,23u,0u,0u},
                   {3567587328u,232u,0u,0u},
                   {1316134912u,2328u,0u,0u},
                   {276447232u,23283u,0u,0u},
                   {2764472320u,232830u,0u,0u},
                   {1874919424u,2328306u,0u,0u},
                   {1569325056u,23283064u,0u,0u},
                   {2808348672u,232830643u,0u,0u},
                   {2313682944u,2328306436u,0u,0u},
                   {1661992960u,1808227885u,5u,0u},
                   {3735027712u,902409669u,54u,0u},
                   {2990538752u,434162106u,542u,0u},
                   {4135583744u,46653770u,5421u,0u},
                   {2701131776u,466537709u,54210u,0u},
                   {1241513984u,370409800u,542101u,0u},
                   {3825205248u,3704098002u,5421010u,0u},
                   {3892314112u,2681241660u,54210108u,0u},
                   {268435456u,1042612833u,542101086u,0u},
                   {2684354560u,1836193738u,1126043566u,1u},
                   {1073741824u,1182068202u,2670501072u,12u},
                   {2147483648u,3230747430u,935206946u,126u},
                   {0u,2242703233u,762134875u,1262u},
                   {0u,952195850u,3326381459u,12621u},
                   {0u,932023908u,3199043520u,126217u},
                   {0u,730304488u,1925664130u,1262177u},
                   {0u,3008077584u,2076772117u,12621774u},
                   {0u,16004768u,3587851993u,126217744u},
                   {0u,160047680u,1518781562u,1262177448u}};

void print128(ui128 x)
{
    int i = 38;
    int z = 0;
    while (i >= 0)
    {
        int c = 0;
        while (ge128(x, deci128[i]))
        {
            c++; sub128(x, deci128[i]);
        }
        if (i==0 || z || c > 0)
        {
            z = 1; putchar('0' + c);
        }
        --i;
    }
}

int main(int argc, const char *argv[])
{
    ui128 test = { 0x12345678, 0x90abcdef, 0xfedcba90, 0x8765421 };
    print128(test);
    return 0;
}

That number in the problem text in decimal becomes

11248221411398543556294285637029484152

and Python agrees this is the correct value (this of course doesn't mean the code is correct!!! ;-) )

Improve this answer

4 Comments

unsigned is not guaranteed to contain 32 bits, 16 bits is the required minimum for it. Use unsigned long instead, which contains at least 32 bits per the standard.
I thought the problem was a very specific one, not a general one. From the text unsigned are 32 bits (OP is using 4 unsigned ints to represent a 128-bit number).
Probably wouldn't be too difficult to modify this to do division by 1,000,000,000 (which is the largest power of 10 representable in a 32-bit value) instead of 10. That would cut down on the operations 9 times.
@Silverhalide: This method was not using any multiplication or division (and is for example useful if the hardware doesn't have those instruction) and the division is implemented as repeated subtraction (therefore I cannot use a 10000 base unless doing up to 10000 loops per digit group). I've added another answer for the modulo approach... the maximum number of digits per iteration is however 4 and not 9 because when computing division/modulo operation you've to consider also the carry. Using 10000 as base allows for four digits and fits into 16 bits.
2

Same thing, but with 32-bit integer arithmetic:

#include <stdio.h>

unsigned short a [] = { 
  0x0876, 0x5421,
  0xfedc, 0xba90,
  0x90ab, 0xcdef,
  0x1234, 0x5678
};

int
main ()
{
  unsigned int d, r;

  do
    {
      r = a [0];

      d = r / 10;
      r = ((r - d * 10) << 16) + a [1];
      a [0] = d;

      d = r / 10;
      r = ((r - d * 10) << 16) + a [2];
      a [1] = d;

      d = r / 10;
      r = ((r - d * 10) << 16) + a [3];
      a [2] = d;

      d = r / 10;
      r = ((r - d * 10) << 16) + a [4];
      a [3] = d;

      d = r / 10;
      r = ((r - d * 10) << 16) + a [5];
      a [4] = d;

      d = r / 10;
      r = ((r - d * 10) << 16) + a [6];
      a [5] = d;

      d = r / 10;
      r = ((r - d * 10) << 16) + a [7];
      a [6] = d;

      d = r / 10;
      r = r - d * 10;
      a [7] = d;

      printf ("%d\n", r);
    }
  while (a[0] || a[1] || a[2] || a[3] || a [4] || a [5] || a[6] || a[7]);


  return 0;
}
Improve this answer

Comments

0

You actually don't need to implement long division. You need to implement multiplication by a power of two, and addition. You have four uint_32. First convert each of them to a string. Multiply them by (2^32)^3, (2^32)^2, (2^32)^1, and (2^32)^0 respectively, then add them together. You don't need to do the base conversion, you just need to handle putting the four pieces together. You'll obviously need to make sure the strings can handle a number up to UINT_32_MAX*(2^32)^3.

Improve this answer

2 Comments

+1 A custom base-10 bignum library is a good idea, but "multiplication by a power of two" is not specially easy in base 10. The OP will have to do general multiplication.
Anyway, one has to implement the multiplication of "strings". That is, treat strings as decimal digits and do the multiplication
0

Supposing you have a fast 32-bit multiplication and division the result can be computed 4 digits at a time by implementing a bigint division/modulo 10000 and then using (s)printf for output of digit groups.

This approach is also trivial to extend to higher (or even variable) precision...

#include <stdio.h>

typedef unsigned long bigint[4];

void print_bigint(bigint src)
{
    unsigned long int x[8];   // expanded version (16 bit per element)
    int result[12];           // 4 digits per element
    int done = 0;             // did we finish?
    int i = 0;                // digit group counter

    /* expand to 16-bit per element */
    x[0] = src[0] & 65535;
    x[1] = src[0] >> 16;
    x[2] = src[1] & 65535;
    x[3] = src[1] >> 16;
    x[4] = src[2] & 65535;
    x[5] = src[2] >> 16;
    x[6] = src[3] & 65535;
    x[7] = src[3] >> 16;

    while (!done)
    {
        done = 1;
        {
            unsigned long carry = 0;
            int j;
            for (j=7; j>=0; j--)
            {
                unsigned long d = (carry << 16) + x[j];
                x[j] = d / 10000;
                carry = d - x[j] * 10000;
                if (x[j]) done = 0;
            }
            result[i++] = carry;
        }
    }

    printf ("%i", result[--i]);
    while (i > 0)
    {
        printf("%04i", result[--i]);
    }
}

int main(int argc, const char *argv[])
{
    bigint tests[] = { { 0, 0, 0, 0 },
                       { 0xFFFFFFFFUL, 0, 0, 0 },
                       { 0, 1, 0, 0 },
                       { 0x12345678UL, 0x90abcdefUL, 0xfedcba90UL, 0x8765421UL } };
    {
        int i;
        for (i=0; i<4; i++)
        {
            print_bigint(tests[i]);
            printf("\n");
        }
    }
    return 0;
}
Improve this answer

Comments

0

@Alexey Frunze's method is easy but it's very slow. You should use @chill's 32-bit integer method above. Another easy method without any multiplication or division is double dabble. This may work slower than chill's algorithm but much faster than Alexey's one. After running you'll have a packed BCD of the decimal number

Improve this answer

Comments

0

On github is an open source project (c++) which provides a class for a datatype uint265_t and uint128_t.

https://github.com/calccrypto/uint256_t

No, I' not affiliated with that project, but I was using it for such a purpose, but I guess it could be usefull for others as well.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.