How to convert an arbitrary length unsigned int array to a base 10 string representation?

Question

I am currently working on an arbitrary size integer library for learning purposes.

Each number is represented as uint32_t *number_segments.

I have functional arithmetic operations, and the ability to print the raw bits of my number.

However, I have struggled to find any information on how I could convert my arbitrarily long array of uint32 into the correct, and also arbitrarily long base 10 representation as a string.

Essentially I need a function along the lines of:

std::string uint32_array_to_string(uint32_t *n, size_t n_length);

Any pointers in the right direction would be greatly appreciated, thank you.

Do you know how to do long division? By hand? Do the same here. — Sam Varshavchik, Jun 05 '22 at 21:22
The [source code for a Java BigInteger](https://developer.classpath.org/doc/java/math/BigInteger-source.html) has a "format" function (down on line 1471) and a bunch of `toString` stuff. That may give you some clues. — Adrian Mole, Jun 05 '22 at 21:24
@SamVarshavchik how do you propose exactly that I apply long division? — Mr_IO, Jun 05 '22 at 21:26
@AdrianMole I will try an decipher it, thanks for the resource — Mr_IO, Jun 05 '22 at 21:27
@AdrianMole awesome. Is this from the GNU-java compiler they used to have? — Aykhan Hagverdili, Jun 05 '22 at 21:31
If you can work in base 1000000000 instead of base 4294967296, this becomes much easier. See https://stackoverflow.com/a/22004815/5987 — Mark Ransom, Jun 06 '22 at 01:39

Goswin von Brederlow · Accepted Answer · 2022-06-06T01:32:30.833

1

You do it the same way as you do with a single uint64_t except on a larger scale (bringing this into modern c++ is left for the reader):

char * to_str(uint64_t x) {
    static char buf[23] = {0}; // leave space for a minus sign added by the caller
    char *p = &buf[22];
    do {
      *--p = '0' + (x % 10);
      x /= 10;
    } while(x > 0);
    return p;
}

The function fills a buffer from the end with the lowest digits and divides the number by 10 in each step and then returns a pointer to the first digit.

Now with big nums you can't use a static buffer but have to adjust the buffer size to the size of your number. You probably want to return a std::string and creating the number in reverse and then copying it into a result string is the way to go. You also have to deal with negative numbers.

Since a long division of a big number is expensive you probably don't want to divide by 10 in the loop. Rather divide by 1'000'000'000 and convert the remainder into 9 digits. This should be the largest power of 10 you can do long division by a single integer, not bigum / bignum. Might be you can only do 10'000 if you don't use uint64_t in the division.

edited Jun 06 '22 at 01:32

answered Jun 06 '22 at 01:23

Goswin von Brederlow

11,875
2
24
42

Returning a pointer to a local variable that has gone out of scope is undefined behavior. – Mark Ransom Jun 06 '22 at 01:28
@MarkRansom the buffer was supposed to be static, that got lost somehow. fixed. – Goswin von Brederlow Jun 06 '22 at 01:32
Thank you so much, it will take me a bit to implement everything but I believe that your answer has everything necessary. Cheers! – Mr_IO Jun 06 '22 at 04:14
1

Division by a constant can also be done by multiplication with `2^i / x` and shifting the result by `i`. This can give you an `O(n)` division and remainder. – Goswin von Brederlow Jun 06 '22 at 04:29

How to convert an arbitrary length unsigned int array to a base 10 string representation?

1 Answers1