C: Representation of Big Integers

Question

So, let's say I've created a struct of 3 32-bit integers that act as a 96-bit integer.

typedef struct {
    unsigned int x, y, z;
} Int96; 

Let's take this to mean that int x is the first integer to be filled. Before it overflows, y is incremented and x is refreshed back to 0. z functions similarly, but takes care of y's overflow.

How would I go about printing the value stored in this struct? Surely I can't directly print out the full value without causing an overflow on my system.

Answer 1

The first step is writing general purpose arithmetic routines for your Int96:

void Add96(Int96 *a, const Int96 *b) {
    // add b to a
    a->x += b->x;
    a->y += b->y;
    a->z += b->z;
    if (a->y < b->y) a->z++;
    if (a->x < b->x && ++a->y == 0) a->z++; }
void Sub96(Int96 *a, const Int96 *b);
void Mul96(Int96 *a, const Int96 *b);
void Div96(Int96 *a, const Int96 *b);
void Mod96(Int96 *a, const Int96 *b);

With those you can write:

void print96(const Int96 *val) {
    Int96 ten = { 10, 0, 0 };
    Int96 div = *val;
    Int96 mod = *val;
    Div96(&div, &ten);
    Mod96(&mod, &ten);
    if (div.x || div.y || div.z) print96(&div);
    putchar('0' + mod.x); }

You can make this more efficient by writing a DivMod96uint function that does the div and mod in a single step and takes an unsigned (rather than an Int96) for the second argument and returns the mod. You can also avoid an extra copy per digit by having a print96destructive function that overwrites its argument, and have print96 just make a copy and then call that:

void print96destructive(Int96 *val) {
    unsigned mod = DivMod96ui(val, 10);
    if (val->x || val->y || val->z) print96destructive(val);
    putchar('0' + mod); }
void print96(const Int96 *val) {
    Int96 v = *val;
    print96destructive(&v); }

unsigned DivMod96ui(Int96 *a, unsigned b) {
    unsigned mod = a->z % b;
    a->z /= b;
    uint64_t y = a->y + ((uint64_t)mod << 32);
    mod = y % b;
    a->y = y / b;
    uint64_t x = a->x + ((uint64_t)mod << 32);
    mod = x % b;
    a->x = x / b;
    return mod; }