Impression grande base de base de 256 dans la base 10 dans c

Question

J'ai un tableau de caractères non signés dans c Je suis en train d'imprimer en base 10, et je suis coincé. Je pense que ce sera mieux expliqué dans le code, donc, étant donné:

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

Je voudrais imprimer 197121.

Ceci est trivial avec petite base 256 tableaux. On peut simplement 1 * 256^0 + 2 * 256^1 + 3 * 256^2.

Cependant, si mon tableau était grand de 100 octets, alors cela devient rapidement un problème. Il n'y a pas de type intégral dans C qui soit de 100 octets, ce qui explique pourquoi je stocke des nombres dans des tableaux de chars non signés pour commencer.

Comment suis-je supposé imprimer efficacement ce numéro en base 10?

Je suis un peu perdu.

Answer 1

Il n'existe aucun moyen simple de le faire en utilisant uniquement la bibliothèque C standard. Vous devrez soit écrire la fonction vous-même (non recommandé), soit utiliser une bibliothèque externe telle que GMP.

Par exemple, en utilisant GMP, vous pourriez faire:

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

Voici une fonction qui fait ce que vous voulez:

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

Cela semble parfaitement lisible pour moi. Il suffit de passer le tableau unsigned char * que vous voulez convertir et la taille. Notez que ce ne sera pas parfait - pour une précision arbitraire, je suggère de regarder dans la bibliothèque GNU MP BigNum, comme cela a déjà été suggéré.

En prime, je n'aime pas votre stockage de vos numéros dans l'ordre petit-boutiste, alors voici une version si vous voulez stocker la base-256 numéros dans l'ordre 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; 
} 

Juste choses à considérer.

Answer 3

Quand j'ai vu cette question, j'ai l'intention de la résoudre, mais à ce moment j'étais très occupé. La fin de semaine dernière, j'ai pu gagner quelques heures de temps libre, alors j'ai considéré mon défi en attente.

Tout d'abord, je vous suggère de considérer la réponse ci-dessus. Je n'utilise jamais de bibliothèque GMP mais je suis sûr que c'est une meilleure solution qu'un code fait à la main. En outre, vous pourriez être intéressé à analyser le code de la calculatrice bc; ça peut marcher avec de gros nombres et j'ai l'habitude de tester mon propre code.

Ok, si vous êtes toujours intéressé par un code, faites-le vous-même (uniquement avec le langage de support C et la bibliothèque Standard C), je peux vous donner quelque chose.

Avant tout, un peu de théorie. Dans la théorie numérique de base (niveau arithmétique modulaire) theres est un algorithme qui m'inspire pour arriver à une solution; Multiplier and Power algorithme pour résoudre un ^N Module 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; 

où k est le nombre de chiffres moins l'un des N en représentation binaire, et n_i est i chiffre binaire.Par exemple (N est exposant):

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 

Lorsque nous faisons une opération de module, comme une division entière, nous pouvons perdre une partie du nombre, donc nous ne disposons que de modifier l'algorithme pour ne pas manquer les données pertinentes.

Voici mon code (attention à ce que ce soit un code adhoc, une forte dépendance de l'arc informatique.) Je joue avec la longueur de données du langage C, donc attention car mes données ne peuvent pas être identiques:

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

pour compiler:

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

pour vérifier le résultat, utilisez la sortie directe et entrée bc. script shell simple:

#!/bin/bash 


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

echo "Test Finished!"; 

---

Nous avons et tableau de unsigned int (4 octets) où nous à chaque int de tableau un certain nombre de 9 chiffres (% 1000000000UL); donc num [0] nous aurons les 9 premiers chiffres, num [1] nous aurons les chiffres 10 à 18, num [2] ... J'utilise la mémoire convencional pour travailler mais une amélioration peut le faire avec la mémoire dinamique. Ok, mais quelle longueur ça pourrait être le tableau? (ou combien de mémoire devons-nous allouer?). L'utilisation, nous pouvons déterminer le nombre de chiffres calculatrice bc (bc -l avec mathlib) a un numéro:

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

Si nous savons chiffres, nous savons entiers quantité dont nous avions besoin:

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

Si vous travaillez avec valeur telle que (2^k)^N on peut le résoudre logarithme de cette expression:

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

pour déterminer exactement la longueur du réseau entier. Exemple:

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

La valeur 1000000000UL (10^9) est très important constante. Une constante comme 10000000000UL (10^10) ne fonctionne pas parce que peut produire et débordement indétecté (essayez ce qui se passe avec le nombre 16^16 et 10^10 constante) et une constante plus petit comme 1000000000UL (10^8) sont corrects mais nous devons réserver plus de mémoire et faire plus de pas. 10^9 est la constante clé pour un entier non signé de 32 bits et un entier long non signé de 64 bits.

Le code a deux parties, Multiplier (facile) et Puissance par 2 (plus dur). Multiplier est juste une multiplication et une échelle et propager le débordement d'entier. Il faut le principe de la propriété associative en math pour faire exactement le principe inverse, donc si k (A + B + C) on veut kA + kB + kC où le nombre sera k * A * 10^18 + k * B * 10^9 + k C. Obiously, k L'opération C peut générer un nombre supérieur à 999 999 999, mais jamais plus grand que 0xFF FF FF FF FF FF FF. Un nombre supérieur à 64 bits ne peut jamais apparaître dans une multiplication car C est un nombre entier non signé de 32 bits et k est un nombre entier non signé de 16 bits. Dans Worts cas, nous aurons ce numéro:

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; 

Après Mul k B, nous devons ajouter 0x FF FE de la dernière multiplication des C (B = k B + (C/module)), etc. sur (nous avons 18 bits de décalage arithmétique, assez pour garantir des valeurs correctes).

Power est plus complexe, mais est en essencial, le même problème (multiplication et ajoutez), donc je donne quelques astuces sur le pouvoir de code:

• types de données sont importantes, très importantes
• Si vous essayez Pour multiplier un entier non signé avec un entier non signé, vous obtenez un autre entier non signé. Utilisez un cast explicite pour obtenir un long long non signé et ne perdez pas de données.
• Toujours utiliser un modificateur non signé, ne l'oubliez pas!
• Alimentation par 2 peut directement modifier l'index 2 avant l'indice actuel
• gdb est votre ami

J'ai développé une autre méthode qui ajoutent de grands nombres. Ces derniers je ne prouve pas tellement mais je pense que cela fonctionne bien. Ne sois pas cruel avec moi s'il y a un bug.

... et c'est tout!

PD1: Développé dans 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 

nombres tels que 256^1024 il passe:

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

Un bucle qui Calculons i^i i allant i = 1 ... 1024 :

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

Pour les nombres tels que 65355^65355, le temps passé est fou. PD2: Ma réponse est si tardive mais j'espère que mon code sera utile.

PD3: Désolé, expliquez-moi en anglais est l'un de mes pires handicaps!

Dernière mise à jour: Je viens eu une idée avec la même algorithme, mais d'autres la mise en œuvre, améliorer la qualité et réduire la mémoire de quantité à utiliser (on peut utiliser les bits de complètement unsigned int). Le secret: n^2 = n * n = n * (n - 1 + 1) = n * (n - 1) + n. (Je ne ferai pas ce nouveau code, mais si quelqu'un est intéressé, peut être après les examens ...)

Answer 4

Il peut être trop tard ou trop hors de propos pour faire cette suggestion, mais pourriez-vous stocker chaque octet comme deux base 10 chiffres (ou une base 100) au lieu d'une base 256? Si vous n'avez pas encore implémenté la division, cela implique tout ce que vous avez d'addition, de soustraction et peut-être de multiplication; ceux-ci ne devraient pas être trop difficiles à convertir. Une fois que vous avez fait cela, l'imprimer serait trivial.

Answer 5

Je ne sais pas si vous avez encore besoin d'une solution, mais j'ai écrit un article à propos de ce problème. Il montre un algorithme très simple qui peut être utilisé pour convertir un nombre long arbitraire avec la base X en un nombre correspondant de base Y. L'algorithme est écrit en Python, mais il ne fait en réalité que quelques lignes et n'utilise aucun Python. la magie. J'avais aussi besoin d'un tel algorithme pour une implémentation C, mais j'ai décidé de le décrire en utilisant Python pour deux raisons. Tout d'abord, Python est très lisible par quiconque comprend les algorithmes écrits dans un pseudo langage de programmation et, deuxièmement, je ne suis pas autorisé à poster la version C, parce que je l'ai fait pour mon entreprise. Jetez un coup d'oeil et vous verrez comment ce problème peut être résolu en général. Une implémentation en C devrait être simple ...