Stampa grande matrice di base 256 in base 10 in c

Question

Ho un array di caratteri senza segno in c che sto cercando di stampare in base 10, e mi sono bloccato. Credo che questo sarà meglio spiegato nel codice, così, data:

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

Vorrei stampare 197121.

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

Tuttavia, se la mia matrice era di 100 byte di grandi dimensioni, allora questa diventa rapidamente un problema. Non v'è alcun tipo integrale in C che è 100 byte grande, ed è per questo che sto memorizzazione numeri negli array char senza segno per cominciare.

Come faccio a stampare in modo efficiente questo numero in base 10?

Sono un po 'perso.

Answer 1

Non c'è un modo semplice per farlo utilizzando solo la libreria standard C. Potrete sia necessario per scrivere la funzione da soli (non raccomandato), o utilizzare una libreria esterna come ad esempio GMP .

Per 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

Quando ho visto questa domanda, mi propongo di risolverlo, ma in quel momento mi era molto affollato. Questo lo scorso fine settimana ho potuto guadagnare qualche ora di premi di tempo libero così ho considerato la mia sfida in corso.

Prima di tutto, vi suggerisco di considerare al di sopra di risposta. Io non uso mai libreria GMP ma sono sicuro che sia la soluzione migliore di un codice a mano. Inoltre, si potrebbe essere interessante analizzare il codice della calcolatrice bc; Può funziona con i grandi numeri e ho usato per testare il mio codice.

Ok, se siete ancora interessati ad un codice di farlo da soli (solo con il supporto di linguaggio C e la libreria standard C) può essere che posso dare qualcosa.

Prima di tutto, un po 'di teoria po'. In teoria numerica di base (livello di aritmetica modulare) Theres è un algoritmo che mi ispirano per arrivare a una soluzione; Multiply e Power algoritmo per risolvere i a ^ 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 funzionamento del modulo, come divisione intera, possiamo perdere parte del numero, quindi dobbiamo solo modificare algoritmo per non perdere i dati rilevanti.

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 conseguenza, utilizzare l'uscita diretta e ingresso bc. Facile script di shell:

#!/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] dovremo cifre da 10 a 18, num [2] ... Io uso la memoria convencional a lavorare, ma un miglioramento posso farlo con la memoria dinamica. Ok, ma come lunghezza Potrebbe essere la matrice? (O quanti di memoria abbiamo bisogno di 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 avevamo bisogno:

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

Se si lavora con il valore come (2 ^ k) ^ N è possibile risolverlo 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 dovesse funzionare perché può produrre e troppopieno indetected (provate ciò che è accade con il numero 16 ^ 16 e 10 ^ 10 costante) e una costante più piccolo come 1000000000UL (10 ^ 8) sono corrette ma abbiamo bisogno di riservare più memoria e fare più passi. 10 ^ 9 è costante chiave per unsigned int di 32 bit e unsigned long long int di 64 bit.

Il codice ha due parti, moltiplicare (facile) e Power per 2 (più difficile). Moltiplicare è solo moltiplicazione e la scala e propagare l'overflow integer. Ci vuole il principio della proprietà associativa in matematica per fare esattamente il principio inverso, quindi se k (A + B + C) vogliamo kA + kB + kC cui numero sarà k * A * 10 ^ 18 + k * B * 10 ^ 9 + k C. Obiously, k funzionamento C può generare un numero più grande 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 di 32 bit senza segno ek è una breve senza segno di 16 bit. In Worts caso, 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ì via (abbiamo 18 bit ARITHMETIC compensati, sufficiente a garantire valori corretti).

Il potere è più complessa, ma è nel essenziale, lo stesso problema (moltiplicazione e aggiungere), in modo da dare alcuni trucchi sul potere codice:

• I tipi di dati sono importanti, molto importanti
• Se si tenta di moltiplicazione un intero senza segno, con numero intero senza segno, si ottiene un altro numero intero senza segno. Utilizzare cast esplicito per ottenere unsigned long int lungo e non fare loDati SE.
• Usare sempre modificatore non firmato, non lo dimenticare!
• 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 mi dimostrare tanto ma penso che funziona bene. Non essere cruels 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 i numeri, come 65355 ^ 65355, trascorso del tempo è folle.

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

PD3: Ci dispiace, mi spiegare in inglese è una delle mie 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. (Io non faccio questo nuovo codice, ma se qualcuno è interessato, può essere dopo gli esami ...)

Answer 3

Non so se hai ancora bisogno di una soluzione, ma ho scritto un articolo su questo problema. Essa mostra un algoritmo molto semplice che può essere utilizzato per convertire un numero arbitrario lungo con base X ad un corrispondente numero di base di Y. L'algoritmo è scritto in Python, ma è lungo davvero solo poche righe e non utilizza Python Magia. Avevo bisogno di un tale algoritmo per un'implementazione C, anche, ma ha deciso di descriverla con Python per due motivi. In primo luogo, Python è molto leggibile da chiunque che capisce algoritmi scritti in un linguaggio pseudo programmazione e, in secondo luogo, non mi è permesso di inviare la versione C, perché l'ho fatto per la mia azienda. Basta dare un'occhiata e vedrete quanto sia facile questo problema può essere risolto in generale. Un'implementazione in C dovrebbe essere dritto in avanti ...

Answer 4

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

Che sembra perfettamente leggibile per me. Basta passare la matrice unsigned char * che si desidera convertire e la dimensione. Si noti che non sarà perfetto -. Per la precisione arbitraria, suggerisco di guardando nella libreria GNU MP bignum, come è stato 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 ordine big-endian:

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

A soli cose da considerare.

Answer 5

Potrebbe essere troppo tardi o troppo irrilevante per fare questo suggerimento, ma potresti memorizzare ogni byte come due base di 10 cifre (o una base 100) invece di uno di base 256? Se non è stato ancora implementato divisione, poi che implica tutto quello che hai è addizione, sottrazione, moltiplicazione e forse; coloro che non dovrebbe essere troppo difficile da convertire. Una volta fatto questo, la stampa sarebbe banale.