C: Rappresentazione di Big Integers

Question

Quindi, supponiamo di aver creato una struttura di 3 numeri interi a 32 bit che fungono da interi a 96 bit.

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

Prendiamo questo per significare che int x è il primo intero da riempire. Prima che si rovesci, y viene incrementato e x viene aggiornato a 0. z funziona in modo simile, ma si occupa dell'overflow di y.

Come si va a stampare il valore memorizzato in questa struttura? Sicuramente non posso stampare direttamente il valore completo senza causare un overflow sul mio sistema.

Answer 1

Il primo passo è scrivere general purpose routine aritmetiche per la vostra 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); 

Con quelli che si può scrivere:

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

si può fare questo più efficiente scrivendo una funzione DivMod96uint che fa il div e mod in un singolo passo e prende uno unsigned (anziché uno Int96) per il secondo argomento e restituisce il mod. È anche possibile evitare una copia in più per cifre da avere una funzione print96destructive che sovrascrive il suo argomento, e hanno print96 solo fare una copia e quindi chiamare che:

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