C: representation of large integers

Question

So let's say I created a structure of 3 32-bit integers that act like a 96-bit integer.

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

Let this mean that int x is the first integer to be populated. Before it overflows, y is incremented, and x is updated to 0. z is similar, but takes care of overflow y.

How can I print the value stored in this structure? Of course, I cannot directly print the full price without causing my system to overflow.

Answer 1

The first step is to write 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 the ones 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 takes div and mod in one step, and takes the second argument unsigned (not Int96 ) and returns the mod. You can also avoid an extra copy by digit using the print96destructive function, which overwrites its argument and has print96 just to make a copy, and then call this:

 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; }