Big Integer Printing

[Shadowwolf]

For a number-crunching application I found the need to store large integers (usually around 64-128 bytes). The big integers are stored as an array of 64-bit numbers (uint64_t) This design was chosen because the application runs on a 64-bit platform, and the assembly instruction ADC can then be used to easily implement relatively fast and easy addition.

So far the application runs fine, the numbers are being calculated correctly. But currently the only way to print the numbers is to print each 64-bit value separately and show the entire value as an array, then manually check whether this value was correct.

Now to finish the application, it's required to print the values in base-10 representation. Is there any way to implement this? All values used will be unsigned, so there is no need to worry about the sign of the project.

So far I've only been able to output the values as hexadecimal using the following function:

//Prints a large integer, value points to an array holding the value, size contains the array size
void printBigInt(uint64_t* value, uint64_t size)
{
    //The last value in the array contains the most-significant bits, so print the array backwards
    std::cout << std::hex;
    for(uint64_t i = size; i > 0; --i)
    {
        std::cout << value[i-1];
    }
}

Of course this approach does not work in base-10. Is there a way to print the values in base-10?

[codekiddy]

it's required to print the values in base-10 representation. Is there any way to implement this?

maximum integral number which standard defines is 64 bits.

However for binary/decimal output for numbers up to 64 bits there are several ways of achieving this, and the most easy way when dealing with bits is to use std::bitset.

bitset is a template taking count of bits as template parameter.
for example to create a bitset object consisting of 64 bits you declare bitset variable like this:

#include <bitset>
using std::bitset;

#include <iostream>
using std::cout;
using std::endl;

int main()
{
	// create 64bit bitset object
	bitset<64> qword;

	// assign 64bit value
	qword = 0b1001'0000'1100'0011'1111'1111'0000'0000'1001'0000'1100'0011'1111'1111'0000'0000;

	// print the value to output screen
	cout << "binary representation:\t" << qword << endl;

	// to print decimal value
	cout << "decimal representation:\t" << qword.to_ullong();

	return 0;
} 

program output:

binary representation:  1001000011000011111111110000000010010000110000111111111100000000
decimal representation: 10431461539814047488

[naraku9333]

You may want to take a look at boost.multiprecision http://www.boost.org/doc/libs/1_58_0/libs/multiprecision/doc/html/boost_multiprecision/tut/ints/cpp_int.html

[Shadowwolf]

For printing values smaller than 64-bit a regular cout would also work. The values will operate on big integers (larger than 64-bit at least). Boost multiprecision looks promising and will surely do what I intended to do, probably in a more efficient way than I wrote it. So I think I'm going to use that instead of the original design.

Even though, how would one print a self-made big integer value? An example of how the data is stored might help understand the problem better:

//Function declarations
//Add: Performs val1 += val2 using size as the amount of 64-bit numbers stored in the array
extern "C" void bigint_add(uint64_t* val1, uint64_t* val2, uint64_t size); //Implemented in assembly

//Somewhere down the main function
uint64_t val1[] = {std::numeric_limits<uint64_t>::max(), 0x00};
uint64_t val2[] = {0x01, 0x00};

bigint_add(val1, val2, 2); //val1 += val2
//Val1 is now {0x00, 0x01} 

This is a trivial example which could be solved by using 128-bit integer math, but in the real program the number of uint64_t used to represent the number will be determined dynamically. A possible solution I thought of would be to use integer division and modulo:

void print_bigint(uint64_t* value, uint64_t size)
{
    if(bigint_equals(value, size, 0)) //Check for 0, special case
    {
        std::cout << "0";
        return;
    }
    uint64_t* cpyvalue = bigint_copy(value, size); //Copy the value
    while(!bigint_equals(cpyvalue, size, 0)) //Continue as long as not zero
    {
        uint64_t remainder;
        bigint_divide(cpyvalue, size, 10, &remainder); //cpyvalue /= 10, remainder stored in the remainder variable
        std::cout << remainder;
    }
    bigint_delete(cpyvalue); //Delete the copy
}

This seems to work, but it involves implementing quite expensive functions. Division is implemented using repeated subtraction. Are there more efficient ways to design such an algorithm?

[dhayden]

Even though, how would one print a self-made big integer value?

If the numbers is really a binary number then you have to do it the same way as with smaller numbers: divide by 10, take the remainder, lather rinse repeat.

Or to avoid the division:
- start with tmp=1
- Multiply by 10 until tmp>n
- Take the previous value of tmp and
- repeatedly subtract tmp from n until n< tmp. Count the number of times you subtract
- print that number.
- repeat.

For example, to print 467:
- tmp=1
- keep multiplying until tmp=1000
- take previous value: tmp=100
- subtract : 467-100-100-100-100 = 67
- print 4 (the number of times you subtracted.
- repeat to process to print 67.


The other option is to not store the numbers in binary in the first place. For example, you might store it in base 1,000,000,000 where each 32-bit value stores a base 1 billion digit. This makes the arithmetic a little more complex but printing it gets much easier.

That can be extended all the way down to binary-coded decimal where you store a single base-ten digit in a 4 but field. With this method, arithmetic is hard by printing is trivial.

[Shadowwolf]

Since most of the resulting application involves arithmetic on the number, I think it might be a better approach to keep using binary, since the arithmetic can be executed using a simple loop around the ADC and SBB instructions. The printing is only when all computations are done.

I'm going to profile both the division by 10 and the non-division method (taking a look at the code required to run both). Then pick whichever seems to be the better alternative. Thank all of you for the help.