Stampa matrice 256 di base grande nella base 10 in c

Question

Ho una matrice di caratteri non firmati in c Sto tentando di stampare nella base 10 e sono bloccato. Credo che questo verrà meglio spiegato nel codice, quindi, data:

unsigned char n[3]; 
char[0] = 1; 
char[1] = 2; 
char[2] = 3; 

desidero stampare 197121.

Questo è banale con piccola base 256 array. Uno può semplicemente 1 * 256^0 + 2 * 256^1 + 3 * 256^2.

Tuttavia, se il mio array era grande 100 byte, questo diventa rapidamente un problema. Non esiste un tipo integrale in C che sia grande 100 byte, motivo per cui sto memorizzando i numeri in array di char non firmati per cominciare.

Come si suppone di stampare in modo efficiente questo numero nella base 10?

Sono un po 'perso.

Answer 1

Non esiste un modo semplice per farlo utilizzando solo la libreria C standard. Dovrai scrivere tu stesso la funzione (non consigliato) o utilizzare una libreria esterna come GMP.

Ad esempio, utilizzando GMP, si potrebbe fare:

unsigned char n[100]; // number to print 

mpz_t num; 
mpz_import(num, 100, -1, 1, 0, 0, n); // convert byte array into GMP format 
mpz_out_str(stdout, 10, num); // print num to stdout in base 10 
mpz_clear(num); // free memory for num 

Answer 2

Ecco una funzione che fa quello che si vuole:

#include <math.h> 
#include <stddef.h> // for size_t 

double getval(unsigned char *arr, size_t len) 
{ 
    double ret = 0; 
    size_t cur; 
    for(cur = 0; cur < len; cur++) 
     ret += arr[cur] * pow(256, cur); 
    return ret; 
} 

Questo sembra perfettamente leggibile per me. Basta passare l'array unsigned char * che si desidera convertire e la dimensione. Si noti che non sarà perfetto - per precisione arbitraria, suggerisco di guardare nella libreria GNNMP BigNum, come già suggerito.

Come bonus, non mi piace il tuo memorizzare i numeri in ordine little-endian, quindi ecco una versione se si desidera memorizzare base-256 numeri in big-endian ordine:

#include <stddef.h> // for size_t 

double getval_big_endian(unsigned char *arr, size_t len) 
{ 
    double ret = 0; 
    size_t cur; 
    for(cur = 0; cur < len; cur++) 
     { 
     ret *= 256; 
     ret += arr[cur]; 
     } 
    return ret; 
} 

Proprio cose da considerare.

Answer 3

Quando ho visto questa domanda, ho lo scopo di risolverlo, ma in quel momento ero molto occupato. Questo ultimo fine settimana ho potuto guadagnare alcune ore di premio di tempo libero, quindi ho considerato la mia sfida in sospeso.

Prima di tutto, ti suggerisco di considerare la risposta sopra. Non uso mai la libreria GMP, ma sono sicuro che è una soluzione migliore di un codice fatto a mano. Inoltre, potresti essere interessato ad analizzare il codice del calcolatore di bc; può funzionare con grandi numeri e ho usato per testare il mio codice.

Ok, se sei ancora interessato a un codice fallo da solo (solo con il linguaggio di supporto C e la libreria C standard) posso essere in grado di darti qualcosa.

Prima di tutto, un po 'di teoria. Nella teoria numerica di base (livello aritmetico modulare) c'è un algoritmo che mi ispira ad arrivare a una soluzione; Moltiplicare energetica algoritmo per risolvere un ^N modulo m:

Result := 1; 
for i := k until i = 0 
    if n_i = 1 then Result := (Result * a) mod m; 
    if i != 0 then Result := (Result * Result) mod m; 
end for; 

dove K è il numero di cifre meno uno di N in rappresentazione binaria, ed è n_i i cifre binarie.Per esempio (N è esponente):

N = 44 -> 1 0 1 1 0 0 

k = 5 
n_5 = 1 
n_4 = 0 
n_3 = 1 
n_2 = 1 
n_1 = 0 
n_0 = 0 

Quando facciamo un'operazione modulo, come divisione intera, si può perdere parte del numero, quindi dobbiamo solo modificare algoritmo per non perdere i dati pertinenti.

Ecco il mio codice (. Fare attenzione che si tratta di un codice ad hoc, forte dipendenza di arco computer può Fondamentalmente io gioco con lunghezza dei dati del linguaggio C in modo, sia con attenzione perché la mia lunghezza dei dati non poteva essere lo stesso):

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <math.h> 


enum { SHF = 31, BMASK = 0x1 << SHF, MODULE = 1000000000UL, LIMIT = 1024 }; 


unsigned int scaleBigNum(const unsigned short scale, const unsigned int lim, unsigned int *num); 
unsigned int pow2BigNum(const unsigned int lim, unsigned int *nsrc, unsigned int *ndst); 
unsigned int addBigNum(const unsigned int lim1, unsigned int *num1, const unsigned int lim2, unsigned int *num2); 

unsigned int bigNum(const unsigned short int base, const unsigned int exp, unsigned int **num); 


int main(void) 
{ 
    unsigned int *num, lim; 
    unsigned int *np, nplim; 
    int i, j; 


    for(i = 1; i < LIMIT; ++i) 
    { 
    lim = bigNum(i, i, &num); 

    printf("%i^%i == ", i, i); 
    for(j = lim - 1; j > -1; --j) 
     printf("%09u", num[j]); 
    printf("\n"); 

    free(num); 
    } 

    return 0; 
} 


/* 
    bigNum: Compute number base^exp and store it in num array 
    @base: Base number 
    @exp: Exponent number 
    @num: Pointer to array where it stores big number 

    Return: Array length of result number 
*/ 
unsigned int bigNum(const unsigned short int base, const unsigned int exp, unsigned int **num) 
{ 
    unsigned int m, lim, mem; 
    unsigned int *v, *w, *k; 


    //Note: mem has the exactly amount memory to allocate (dinamic memory version) 
    mem = ((unsigned int) (exp * log10((float) base)/9)) + 3; 
    v = (unsigned int *) malloc(mem * sizeof(unsigned int)); 
    w = (unsigned int *) malloc(mem * sizeof(unsigned int)); 

    for(m = BMASK; ((m & exp) == 0) && m; m >>= 1) ; 

    v[0] = (m) ? 1 : 0; 
    for(lim = 1; m > 1; m >>= 1) 
    { 
    if(exp & m) 
     lim = scaleBigNum(base, lim, v); 

    lim = pow2BigNum(lim, v, w); 

    k = v; 
    v = w; 
    w = k; 
    } 

    if(exp & 0x1) 
    lim = scaleBigNum(base, lim, v); 

    free(w); 

    *num = v; 
    return lim; 
} 

/* 
    scaleBigNum: Make an (num[] <- scale*num[]) big number operation 
    @scale: Scalar that multiply big number 
    @lim: Length of source big number 
    @num: Source big number (array of unsigned int). Update it with new big number value 

    Return: Array length of operation result 
    Warning: This method can write in an incorrect position if we don't previous reallocate num (if it's necessary). bigNum method do it for us 
*/ 
unsigned int scaleBigNum(const unsigned short scale, const unsigned int lim, unsigned int *num) 
{ 
    unsigned int i; 
    unsigned long long int n, t; 


    for(n = 0, t = 0, i = 0; i < lim; ++i) 
    { 
    t = (n/MODULE); 
    n = ((unsigned long long int) scale * num[i] ); 

    num[i] = (n % MODULE) + t; // (n % MODULE) + t always will be smaller than MODULE 
    } 

    num[i] = (n/MODULE); 

    return ((num[i]) ? lim + 1 : lim); 
} 


/* 
    pow2BigNum: Make a (dst[] <- src[] * src[]) big number operation 
    @lim: Length of source big number 
    @src: Source big number (array of unsigned int) 
    @dst: Destination big number (array of unsigned int) 

    Return: Array length of operation result 
    Warning: This method can write in an incorrect position if we don't previous reallocate num (if it's necessary). bigNum method do it for us 
*/ 
unsigned int pow2BigNum(const unsigned int lim, unsigned int *src, unsigned int *dst) 
{ 
    unsigned int i, j; 
    unsigned long long int n, t; 
    unsigned int k, c; 


    for(c = 0, dst[0] = 0, i = 0; i < lim; ++i) 
    { 
    for(j = i, n = 0; j < lim; ++j) 
    { 
     n = ((unsigned long long int) src[i] * src[j]); 
     k = i + j; 

     if(i != j) 
     { 
     t = 2 * (n % MODULE); 
     n = 2 * (n/MODULE); 

     // (i + j) 
     dst[k] = ((k > c) ? ((c = k), 0) : dst[k]) + (t % MODULE); 
     ++k; // (i + j + 1) 
     dst[k] = ((k > c) ? ((c = k), 0) : dst[k]) + ((t/MODULE) + (n % MODULE)); 
     ++k; // (i + j + 2) 
     dst[k] = ((k > c) ? ((c = k), 0) : dst[k]) + (n/MODULE); 
     } 
     else 
     { 
     dst[k] = ((k > c) ? ((c = k), 0) : dst[k]) + (n % MODULE); 
     ++k; // (i + j) 
     dst[k] = ((k > c) ? ((c = k), 0) : dst[k]) + (n/MODULE); 
     } 

     for(k = i + j; k < (lim + j); ++k) 
     { 
     dst[k + 1] += (dst[k]/MODULE); 
     dst[k] %= MODULE; 
     } 

    } 
    } 

    i = lim << 1; 
    return ((dst[i - 1]) ? i : i - 1); 
} 


/* 
    addBigNum: Make a (num2[] <- num1[] + num2[]) big number operation 
    @lim1: Length of source num1 big number 
    @num1: First source operand big number (array of unsigned int). Should be smaller than second 
    @lim2: Length of source num2 big number 
    @num2: Second source operand big number (array of unsigned int). Should be equal or greater than first 

    Return: Array length of operation result or 0 if num1[] > num2[] (dosen't do any op) 
    Warning: This method can write in an incorrect position if we don't previous reallocate num2 
*/ 
unsigned int addBigNum(const unsigned int lim1, unsigned int *num1, const unsigned int lim2, unsigned int *num2) 
{ 
    unsigned long long int n; 
    unsigned int i; 

    if(lim1 > lim2) 
    return 0; 

    for(num2[lim2] = 0, n = 0, i = 0; i < lim1; ++i) 
    { 
    n = num2[i] + num1[i] + (n/MODULE); 
    num2[i] = n % MODULE; 
    } 

    for(n /= MODULE; n; ++i) 
    { 
    num2[i] += n; 
    n = (num2[i]/MODULE); 
    } 

    return (lim2 > i) ? lim2 : i; 
} 

per compilare:

gcc -o bgn <name>.c -Wall -O3 -lm  //Math library if you wants to use log func 

per controllare il risultato, utilizzare l'uscita diretta e ingresso bc. Facile script:

#!/bin/bash 


select S in ` awk -F '==' '{print $1 " == " $2 }' | bc`; 
do 
    0; 
done; 

echo "Test Finished!"; 

---

Abbiamo e array di unsigned int (4 byte) dove memorizzare ad ogni int dell'array a numero di 9 cifre (% 1000000000UL); quindi num [0] avremo le prime 9 cifre, num [1] avremo cifre da 10 a 18, num [2] ... Io uso la memoria convencional per lavorare ma un miglioramento può farlo con memoria dinamica. Ok, ma quanto potrebbe essere l'array? (o quanti memoria dobbiamo allocare?). Usando la calcolatrice bc (bc -l con mathlib) siamo in grado di determinare il numero di cifre ha un numero:

l(a^N)/l(10)  // Natural logarith to Logarithm base 10 

Se sappiamo cifre, sappiamo quantità interi che ci serviva:

(l(a^N)/(9 * l(10))) + 1  // Truncate result 

Se si lavora con valore, ad esempio (2^k)^N è possibile risolvere il problema logaritmo con questa espressione:

(k*N*l(2)/(9*l(10))) + 1 // Truncate result 

per determinare la lunghezza esattamente di matrice intera. Esempio:

256^800 = 2^(8*800) ---> l(2^(8*800))/(9*l(10)) + 1 = 8*800*l(2)/(9*l(10)) + 1 

Il valore 1000000000UL (10^9) costante è molto importante. Una costante come 10000000000UL (10^10) non funziona perché può produrre un overflow indeterminato (prova cosa succede con il numero 16^16 e 10^10 costante) e una costante più piccola come 1000000000UL (10^8) sono corrette ma dobbiamo prenotare più memoria e fare più passaggi. 10^9 è la costante di chiave per unsigned int di 32 bit e unsigned long long int di 64 bit.

Il codice ha due parti, Moltiplica (facile) e Aumenta di 2 (più difficile). Moltiplicare è solo moltiplicazione e scala e propagare l'overflow intero. Prende il principio della proprietà associativa in matematica per fare esattamente il principio inverso, quindi se k (A + B + C) vogliamo kA + kB + kC dove il numero sarà k * A * 10^18 + k * B * 10^9 + k C. Obrosamente, k operazione C può generare un numero maggiore di 999 999 999, ma mai più grande di 0xFF FF FF FF FF FF FF FF. Un numero maggiore di 64 bit non può mai verificarsi in una moltiplicazione perché C è un numero intero senza segno di 32 bit e k è un corto senza segno di 16 bit. In caso mosto, avremo questo numero:

k = 0x FF FF; 
C = 0x 3B 9A C9 FF; // 999999999 
n = k*C = 0x 3B 9A | 8E 64 36 01; 

n % 1000000000 = 0x 3B 99 CA 01; 
n/1000000000 = 0x FF FE; 

Dopo Mul k B bisogna aggiungere 0x FF FE dall'ultimo moltiplicazione di C (B = k B + (C/modulo)), e così on (abbiamo un offset aritmetico di 18 bit, sufficiente per garantire i valori corretti).

potenza è più complessa, ma è in essenziale, lo stesso problema (moltiplicazione e aggiungere), in modo da dare alcuni trucchi su codice potenza:

• tipi di dati sono importante, molto importante
• Se si tenta per moltiplicare un intero senza segno con un numero intero senza segno, ottieni un altro intero senza segno. Usa il cast esplicito per ottenere unsigned long long int e non perdere dati.
• Usa sempre il modificatore senza segno, non dimenticarlo!
• Potere da 2 può modificare direttamente 2 indice davanti indice corrente
• gdb è tuo amico

ho sviluppato un altro metodo che aggiungono grandi numeri. Questi ultimi non dimostrano tanto ma penso che funzioni bene. Non essere crudele con me se ha un bug.

... e questo è tutto!

PD1: Sviluppato in un

Intel(R) Pentium(R) 4 CPU 1.70GHz 

Data length: 
    unsigned short: 2 
    unsigned int: 4 
    unsigned long int: 4 
    unsigned long long int: 8 

numeri come 256^1024 la spesa IT:

real 0m0.059s 
user 0m0.033s 
sys 0m0.000s 

Un bucle che è calcolo I^i dove i va per i = 1 ... 1024 :

real 0m40.716s 
user 0m14.952s 
sys 0m0.067s 

Per numeri come 65355^65355, il tempo trascorso è folle.

PD2: La mia risposta è tardiva, ma spero che il mio codice sarà utile.

PD3: Scusate, spiegarmi in inglese è uno dei miei peggiori handicap!

Ultimo aggiornamento: Ho appena avuto un'idea che con stesso algoritmo ma altre implementazioni, migliorare la risposta e ridurre la memoria importo da utilizzare (possiamo usare i bit di completamente unsigned int). Il segreto: n^2 = n * n = n * (n - 1 + 1) = n * (n - 1) + n. (Non eseguirò questo nuovo codice, ma se qualcuno è interessato, potrebbe essere dopo gli esami ...)

Answer 4

Potrebbe essere troppo tardi o troppo irrilevante per fare questo suggerimento, ma potresti memorizzare ogni byte come due base 10 cifre (o una base 100) invece di una base 256? Se non hai ancora implementato la divisione, significa che tutto ciò che hai è addizione, sottrazione e forse moltiplicazione; quelli non dovrebbero essere troppo difficili da convertire. Una volta fatto ciò, la stampa sarebbe banale.

Answer 5

Non so se è ancora necessaria una soluzione, ma ho scritto uno article su questo problema. Mostra un algoritmo molto semplice che può essere usato per convertire un numero arbitrario lungo con la base X in un corrispondente numero di base Y. L'algoritmo è scritto in Python, ma in realtà è solo poche righe e non usa alcun Python Magia. Avevo bisogno di un tale algoritmo per un'implementazione C, ma decisi di descriverlo usando Python per due ragioni. Innanzitutto, Python è molto leggibile da chiunque comprenda gli algoritmi scritti in un linguaggio di pseudo programmazione e, in secondo luogo, non sono autorizzato a pubblicare la versione C, perché l'ho fatto per la mia azienda. Basta dare un'occhiata e vedrai quanto sia facile risolvere questo problema in generale. Un'implementazione in C dovrebbe essere semplice ...