manually printing a N-byte integer

Question

What is a scalable algorithm to print an N-binary-digit integer manually whose value does not fit in long long. I know printf and friends, along with <iostream> (which most likely piggy-backs on <cstdio> have this builtin for standard types, but I'd like to do it for an integer composed of N bytes.

I have thought about this and googled a bit, but it always comes down to using a pre-existing bigint libirary like GMP (a codebase I am not at all familiar with) or "use printf" or the most helpful "this is difficult".

The integer is basically:

template<size_t N>
class Integer{
...
private:
    int8_t first;
    uint8_t rest[N-1];
}

so reinterpreting an Integer<4>'s bytes would get you an int32_t. I'd like to scale this to N>8. Efficiency is not really my concern at the moment. Neither is endianness (this is for x86).

Quits

I take it you need to print the number in decimal? – Pasahow

@aix yes decimal would be the idea. – Quits

My advice would be to use a bigint library anyway; those libraries are debugged and proven. How will you find flaws in your own coding ? It is not as if you are going to verify the results with pen & paper or in Excel. – Phenothiazine

@tomdemuyt, generating test cases of both decimal and hex representation of big numbers is trivial in Python for example. – Countrified

Answer 1

Step 1: Define a lookup table containing powers of two in string format:

const char * const powers_of_two[] = {"1", "2", "4", "8", "16", "32", "64", ...};

Step 2: Write a function that adds two numbers in string format.

Step 3: Iterate through the bits in your number and add all the strings corresponding to the 1 bits.

Step 4: Print the result.

I used this approach myself for printing very large floating point numbers, and it worked fine for me.

Carabao

You don't even need the table of powers of 2: just add the number to itself to multiply by 2; add 1 to the number if a bit is 1; repeat ==> profit – Vetavetch

Note that it only works for positive numbers, although that's easily fixed. Brilliant. – Countrified

A table of powers of two would be unwieldy to keep track of for arbitrarily large N... – Quits

Answer 2

A basic recursive algorithm for outputting a decimal number:

void negate(Integer & number); // modifies the input
int divide_by_10(Integer & number); // modifies the input
bool is_zero(const Integer & number);

void output_number(Integer number)
{
    if (number.first < 0)
    {
        cout << "-";
        negate(number);
    }
    if (is_zero(number))
    {
        cout << "0";
        return;
    }
    int remainder = divide_by_10(number);
    if (!is_zero(number))
        output_number(number);
    char digit[] = {'0', 0};
    digit[0] += remainder;
    cout << digit;
}

I've left the helper functions undefined for now, perhaps this is enough.

Countrified

Thanks. I don't have any arithmetic (I wanted to be able to see the result first), so I'll try @Fred's suggestion first. I can later compare the performance of both approaches. – Quits