Imprimir base grande 256 matriz en base 10 en c

Question

Tengo una serie de caracteres sin signo en c Estoy intentando imprimir en la base 10, y estoy atascado. Creo que esto se explicará mejor en el código, por lo que, teniendo en cuenta:

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

quisiera imprimir 197121.

Esto es trivial con la pequeña base de 256 matrices. Uno puede simplemente 1 * 256^0 + 2 * 256^1 + 3 * 256^2.

Sin embargo, si mi matriz era de 100 bytes, entonces esto se convierte rápidamente en un problema. No hay un tipo integral en C que tenga 100 bytes de tamaño, razón por la cual estoy almacenando números en matrices char sin signo para empezar.

¿Cómo se supone que debo imprimir de manera eficiente este número en la base 10?

Estoy un poco perdido.

Answer 1

No hay una manera fácil de hacerlo utilizando solo la biblioteca C estándar. Tendrá que escribir la función usted mismo (no recomendado), o usar una biblioteca externa como GMP.

Por ejemplo, el uso de GMP, se podría hacer:

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

Aquí es una función que hace lo que quiere:

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

Eso se ve perfectamente legible para mí. Solo pase la matriz unsigned char * que desea convertir y el tamaño. Tenga en cuenta que no será perfecto: para una precisión arbitraria, sugiero buscar en la biblioteca GNU MP BigNum, como ya se ha sugerido.

Como beneficio adicional, no me gusta el almacenamiento de sus números en orden ascendente hacia la izquierda, así que aquí está una versión si desea almacenar la base de 256 números en big-endian orden:

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

Justo cosas para considerar.

Answer 3

Cuando vi esta pregunta, me propongo resolverla, pero en ese momento estaba muy ocupado. Este último fin de semana pude ganar algunas horas de premio de tiempo libre, así que consideré mi desafío pendiente.

Antes que nada, sugiero que considere la respuesta anterior. Nunca uso la biblioteca GMP pero estoy seguro de que es una mejor solución que un código hecho a mano. Además, podría interesarle analizar el código de calculadora de bc; puede funcionar con grandes números y solía probar mi propio código.

Ok, si usted todavía está interesado en un código, hágalo usted mismo (solo con soporte de lenguaje C y biblioteca Standard C) puede que pueda darle algo.

Antes de nada, un poco de teoría. En la teoría numérica básica (nivel aritmético modular) hay un algoritmo que me inspira a llegar a una solución; Multiplicar y Poder algoritmo para resolver a^N módulo 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; 

Donde k es el número de dígitos menos uno de N en representación binaria, y n_i es el dígito binario i.Por ejemplo (N es exponente):

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 

Cuando hacemos una operación de módulo, como una división entera, que puede perder parte de la serie, por lo que sólo tendrá que modificar el algoritmo que no se pierdan los datos pertinentes.

Aquí está mi código (tenga cuidado de que sea un código adhoc, fuerte dependencia del arco de la computadora). Básicamente juego con la longitud de datos del lenguaje C así que sea cuidadoso porque la longitud de mis datos no podría ser la misma:

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

para compilar:

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

para comprobar resultado, utilizar la salida directa como y la entrada a bc. Fácil secuencia de comandos shell:

#!/bin/bash 


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

echo "Test Finished!"; 

---

Tenemos y matriz de int sin signo (4 bytes) donde almacenamos en cada int de la matriz de una serie de 9 dígitos (% 1000000000UL); por lo tanto, num [0] tendremos los primeros 9 dígitos, num [1] tendremos el dígito 10 a 18, num [2] ... Uso memoria convencional para trabajar, pero una mejora puede hacerlo con memoria dinámica. Ok, pero ¿cuánto tiempo podría ser la matriz? (¿o cuánta memoria tenemos que asignar?). Usando la calculadora antes de Cristo (aC -l con MathLib) podemos determinar cuántos dígitos tiene un número:

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

Si sabemos dígitos, sabemos cantidad enteros que necesitábamos:

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

Si se trabaja con valor tal como (2^k)^N se puede resolver logaritmo con esta expresión:

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

para determinar la longitud de exactamente matriz de enteros. Ejemplo:

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

El valor 1000000000UL (10^9) constante es muy importante. Una constante como 10000000000UL (10^10) no funciona porque puede producir desbordamiento indetectable (prueba lo que sucede con el número 16^16 y 10^10 constante) y una constante más pequeña como 1000000000UL (10^8) son correctas, pero necesitamos reservar más memoria y hacer más pasos. 10^9 es la constante clave para unsigned int de 32 bits y unsigned long long int de 64 bits.

El código tiene dos partes, Multiplica (fácil) y Potencia por 2 (más difícil). Multiplicar es solo multiplicación y escala y propagar el desbordamiento de enteros. Toma el principio de propiedad asociativa en matemáticas hacer exactamente el principio inverso, entonces si k (A + B + C) queremos kA + kB + kC donde el número será k * A * 10^18 + k * B * 10^9 + k C. Obviamente, k operación C puede generar un número mayor que 999 999 999, pero nunca más grande que 0xFF FF FF FF FF FF FF. Un número mayor de 64 bits nunca puede ocurrir en una multiplicación porque C es un entero sin signo de 32 bits y k es un corto sin signo de 16 bits. En el caso de los mostos, vamos a tener este número:

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; 

Después de Mul k B tenemos que añadir 0x FF FE de la última multiplicación de C (B = k B + (C/módulo)), y por lo on (tenemos 18 bits de desplazamiento aritmético, suficiente para garantizar valores correctos).

de energía es más complejo, pero está en algo esencial, el mismo problema (multiplicación y añadir), por lo que dan algunos trucos sobre la potencia de código:

• tipos de datos es importante, muy importante
• Si intenta a la multiplicación de un entero sin signo con un entero sin signo, obtiene otro entero sin signo. Use el molde explícito para obtener unsigned long long int y no perder datos.
• Siempre use el modificador sin signo, ¡no lo olvide!
• de energía por 2 puede modificar directamente el índice 2 por delante del índice actual
• GDB es su amigo

he desarrollado otro método que añadir grandes números. Estos últimos no pruebo mucho pero creo que funciona bien. No seas cruel conmigo si tiene un error.

... ¡y eso es todo!

PD1: Desarrollado en 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 

Los números como 256^1024 que pasan:

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

Un bucle que es de cómputo i^i, donde i va a i = 1 ... 1024 :

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

Para números como 65355^65355, el tiempo pasado es una locura.

PD2: Mi respuesta es muy tarde, pero espero que mi código sea útil.

PD3: Disculpe, ¡explíqueme en inglés es una de mis peores desventajas!

Última actualización: acabo de haber tenido una idea que con el mismo algoritmo pero otra aplicación, mejorar la respuesta y reducir la cantidad de memoria a usar (podemos usar los bits de completamente unsigned int). El secreto: n^2 = n * n = n * (n - 1 + 1) = n * (n - 1) + n. (No haré este código nuevo, pero si alguien está interesado, puede ser después de los exámenes ...)

Answer 4

Puede ser demasiado tarde o demasiado irrelevante para hacer esta sugerencia, pero ¿podría almacenar cada byte como dos base 10 dígitos (o una base 100) en lugar de una base 256? Si aún no ha implementado la división, eso implica que todo lo que tiene es suma, resta y tal vez multiplicación; esos no deberían ser demasiado difíciles de convertir. Una vez que haya hecho eso, imprimirlo sería trivial.

Answer 5

No sé si todavía necesita una solución, pero escribí un article acerca de este problema. Muestra un algoritmo muy simple que se puede usar para convertir un número largo arbitrario con base X en un número correspondiente de base Y. El algoritmo está escrito en Python, pero en realidad tiene solo unas pocas líneas y no usa ningún Python. magia. Necesitaba tal algoritmo para una implementación de C, también, pero decidí describirlo usando Python por dos razones. En primer lugar, Python es muy legible por cualquiera que entienda los algoritmos escritos en un pseudo lenguaje de programación y, en segundo lugar, no puedo publicar la versión C, porque lo hice para mi empresa. Solo eche un vistazo y verá qué fácil es que este problema se pueda resolver en general. Una implementación en C debería ser directa ...