Números de longitud variable en C (Numeros muy grandes)

[AlbertoBSD]

Y si bien deben de existir varias librerías que ya lo implementen a su manera no me quería quedar sin implementar mi propia solución.

El programa ahora solo convierte cadenas de números decimales "1234" en su representación binaria en memoria, pero no se engañen esta no es la función strtol, esta puede almacenar numeros (sin signo por el momento) de cualquier longitud siempre y cuando tengamos memoria suficiente.

Vamos a ver un ejemplo de las siguientes cadenas:
"1"
"50"
"200"
"255"
"65535"
"4294967295"
"18446744073709551615"

Código (c) [Seleccionar] Expandir

int main() {
numero *n;
n = valor("1"); //Ejemplo de 1 solo digito
free_numero(n);
n = valor("50"); //Ejemplo de 2 digitos
free_numero(n);
n = valor("200"); //Ejemplo de 3 digitos
free_numero(n);
n = valor("255"); //Maximo numero de 1 byte
free_numero(n);
n = valor("65535"); //Maximo numero de 2 bytes
free_numero(n);
n = valor("4294967295"); //Maximo numero de 4 bytes
free_numero(n);
n = valor("18446744073709551615"); //Maximo numero de 8 bytes
free_numero(n);
}

Salida (Con un poco de depuración)

Código [Seleccionar] Expandir

procesando numero 1
1 x10^0 : numeros[0]->valor: 0x456b30 01
b->valor: 0x456bb0 01
procesando numero 50
5 x10^1 : numeros[0]->valor: 0x451480 32
0 x10^0 : numeros[1]->valor: 0x451470 00
b->valor: 0x451530 32
procesando numero 200
2 x10^2 : numeros[0]->valor: 0x451470 c8
0 x10^1 : numeros[1]->valor: 0x4514f0 00
0 x10^0 : numeros[2]->valor: 0x4514b0 00
b->valor: 0x451500 c8
procesando numero 255
2 x10^2 : numeros[0]->valor: 0x451550 c8
5 x10^1 : numeros[1]->valor: 0x451420 32
5 x10^0 : numeros[2]->valor: 0x451530 05
b->valor: 0x451420 ff
procesando numero 65535
6 x10^4 : numeros[0]->valor: 0x451410 60ea
5 x10^3 : numeros[1]->valor: 0x451510 8813
5 x10^2 : numeros[2]->valor: 0x4514a0 f401
3 x10^1 : numeros[3]->valor: 0x451530 1e
5 x10^0 : numeros[4]->valor: 0x4513e0 05
b->valor: 0x451420 ffff
procesando numero 4294967295
4 x10^9 : numeros[0]->valor: 0x4514f0 00286bee
2 x10^8 : numeros[1]->valor: 0x4514a0 00c2eb0b
9 x10^7 : numeros[2]->valor: 0x4514b0 804a5d05
4 x10^6 : numeros[3]->valor: 0x457210 00093d
9 x10^5 : numeros[4]->valor: 0x4571a0 a0bb0d
6 x10^4 : numeros[5]->valor: 0x457160 60ea
7 x10^3 : numeros[6]->valor: 0x457380 581b
2 x10^2 : numeros[7]->valor: 0x456ff0 c8
9 x10^1 : numeros[8]->valor: 0x457230 5a
5 x10^0 : numeros[9]->valor: 0x4572e0 05
b->valor: 0x457210 ffffffff
procesando numero 18446744073709551615
1 x10^19 : numeros[0]->valor: 0x457180 0000e8890423c78a
8 x10^18 : numeros[1]->valor: 0x4572e0 0000203b9db5056f
4 x10^17 : numeros[2]->valor: 0x457370 00002876e1158d05
4 x10^16 : numeros[3]->valor: 0x457390 000004bfc91b8e
6 x10^15 : numeros[4]->valor: 0x457360 0000a7dcf75015
7 x10^14 : numeros[5]->valor: 0x456ff0 00c05773a57c02
4 x10^13 : numeros[6]->valor: 0x457060 0080ca396124
4 x10^12 : numeros[7]->valor: 0x457000 00409452a303
0 x10^11 : numeros[8]->valor: 0x457080 00
7 x10^10 : numeros[9]->valor: 0x457290 003c534c10
3 x10^9 : numeros[10]->valor: 0x457330 005ed0b2
7 x10^8 : numeros[11]->valor: 0x4571a0 0027b929
0 x10^7 : numeros[12]->valor: 0x4571e0 00
9 x10^6 : numeros[13]->valor: 0x457200 405489
5 x10^5 : numeros[14]->valor: 0x4570d0 20a107
5 x10^4 : numeros[15]->valor: 0x457250 50c3
1 x10^3 : numeros[16]->valor: 0x4572a0 e803
6 x10^2 : numeros[17]->valor: 0x457240 5802
1 x10^1 : numeros[18]->valor: 0x457130 0a
5 x10^0 : numeros[19]->valor: 0x457150 05
b->valor: 0x457840 ffffffffffffffff


Ahora esos son ejemplo que las funciones estándar existentes pueden manejar correctamente

Ahora bien el siguiente numero

Código [Seleccionar] Expandir

98765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210

Código (c) [Seleccionar] Expandir

int main() {
numero *n;
n = valor("98765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210"); //Ejemplo de un Googol???
free_numero(n);
}

Salida sin tanta depuración:

Código [Seleccionar] Expandir



procesando numero 98765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210
b->valor: 0x777b70 ea7ec651d7671ed5de67409bdc172dc9a9d7bbd8302306b3a2e2a0cf7730b39b359cea778e3d200b9b9fb6770c6b95b395e8ab9f1474014c01ce7a3e870aa632c1ce5b705dc9f0a328d297dc436038565411ca0e338c7db56f94881768b143402be103d352ddf1beb8d5d3f59c88bb500306744fbfea44dca84d3c2cca5a88060c7168dfa57b5f86a57dda5ad3d0957639100089ca6ac40c6fbc516e76821e8026d3fce0d3fa4b1a5c5b42f723c67c3801e5b6146b5c44a3c70c7b7f63634f14211881cf4fca1bd9f7d9b8bda6db831e0a06f25384fd4262826ba6498c9ec27623314c5d7222d86a9cdf905544e7d67a056bb74b830615b2a164ba237a3889fd302bd8e092456865c265c8202d61ff55a442dc22547e68935d270fa33825e4cd331378afe199ae4ab2acea2aca6330f4727f244b72569ba75bab5a53ce22e2472f603d57314b8b02b361931bcef98c0911032db9e418e9288359f38c1fdfbe7f6a4d2fed867f76fd66d82cd107278f5ae8ec0033a226a31d2e2415f9eb72e910bfad8c2d7c02e8d44c2689de3587e51162308a50fbb776d016ea5491929011176ec8401dbed59282af7910675df3810d704db4faca2e8b44ab92d06237e872c0deef48718f59edd1541f5366e49dcabd9a00c64ec1c99f23be503b0a559e545702185426b2d94b5d7dac547ae430ebac390487d3d80b8b7b7d7d1cd2a40688f96c286cb522671faa5f272e4dd858d3f6bcbdb10fa70bebbef59aa82c18fdfd622c4b7e215c315373e366e84e0a
el numero necesita 557 bytes



Falta optimizar las funciones, el proceso de multiplicación lo hace mediante sumas continuas, trate de liberar la memoria con forme se va usando para no olvidar ninguna variable pero se me pudo pasar alguna.

Usos que se le pueden dar al programa
Si necesitas algo especializado y almacenar números extremadamente grandes para su posterior uso esta es una buena forma de hacerlo.
Yo en lo personal trabaje con esta aplicación por que necesito una forma de almacenar números de mas de 4096 bits tengan encuenta que en el ejemplo anterior el numero mas grande fue un numero de 557 bytes que son 4456 bits.
El proceso mas tardado es convertir el numero de string a binario. Posteriormente considero que las sumas son algo eficientes cuando los números ya se encuentran en su representación binaria.

Codigo completo:

Código (c) [Seleccionar] Expandir

/*
Twitter @albertobsd
*/

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

typedef unsigned char byte;

typedef struct numero_struct {
byte *valor;
unsigned int bytes;
}numero;

numero *valorBase10(unsigned char n,unsigned char e);
numero *valor(char *n);
unsigned short add(unsigned char a, unsigned char b);
void debug(char*s,unsigned char *ptr,unsigned int l,...);
numero *add_numero(numero *a,numero *b);
numero *copiar(numero* n);

numero *add_numero(numero *a,numero *b) {
numero *c;
unsigned char flag_a = 1,flag_b = 1,valor_a,valor_b,acarreo;
unsigned short valor_c;
unsigned int i = 0,max,entrar =1;
//printf("add_numero\n");
//debug("a->valor",a->valor,a->bytes);
//debug("b->valor",b->valor,b->bytes);
c = calloc(sizeof(numero),1);
max = a->bytes + b->bytes;
c->valor = calloc(max,1);
//printf("while\n");
while(entrar) {
valor_c = 0;
//printf("valor de i: %u\n",i);
//printf("valor de a->bytes: %u\n",a->bytes);
if(i < a->bytes) {
valor_a = a->valor[i];
}
else {
flag_a = 0;
valor_a = 0;
}
//printf("valor de b->bytes: %u\n",b->bytes);
if(i < b->bytes) {
valor_b = b->valor[i];
}
else {
flag_b = 0;
valor_b = 0;
}
if(flag_a || flag_b) {
if(c->valor[i] != 0) {
//printf("valor de c->valor[%i]: 0x%.2x\n",i,c->valor[i]);
valor_c+=c->valor[i];
c->valor[i] = 0;
}
//printf("valor de valor_a: 0x%.2x\n",valor_a);
//printf("valor de valor_b: 0x%.2x\n",valor_b);
valor_c+= add(valor_a,valor_b);
//printf("valor de valor_c: 0x%.4x\n",valor_c);
c->valor[i] = valor_c;
acarreo = valor_c >> 8;
i++;
if(acarreo) {
//printf("valor de acarreo: 0x%.2x\n",acarreo);
c->valor[i] = acarreo;
//printf("valor de c->valor[%i]: %.2x\n",i,c->valor[i]);
}
}
else {
entrar = 0;
}
}
//printf("end while\n");
if(acarreo) {
c->bytes = i+1;
}
else {
c->bytes = i;
}
//printf("bytes: %i\n",c->bytes);
//debug("c->valor",c->valor,c->bytes);
//printf("End add_numero\n");
return c;
}

void free_numero(numero* t) {
if(t) {
if(t->valor) {
memset(t->valor,0,t->bytes);
free(t->valor);
}
memset(t,0,sizeof(numero));
free(t);
}
}

numero *copiar(numero* n) {
numero *t;
t= calloc(sizeof(numero),1);
t->bytes = n->bytes;
t->valor = calloc(t->bytes,1);
memcpy(t->valor,n->valor,t->bytes);
return t;
}

void debug(char *s,unsigned char *ptr,unsigned int l,...) {
va_list args;
int i = 0;
char *buffer;
buffer = calloc(strlen(s)*10,sizeof(char));
va_start(args, l);
vsprintf(buffer,s, args);
printf("%s: 0x%x ",buffer,ptr);
while(ptr && i < l) {
printf("%.2x",ptr[i++]);
}
printf("\n");
va_end(args);
free(buffer);
}

numero *valorBase10(unsigned char n,unsigned char e) {
int i,j;
numero *a,*b,*t,*zero,**tofree;
a = calloc(sizeof(numero),1);
a->bytes = 1;
a->valor = calloc(a->bytes,1);
a->valor[0] = n;
zero = calloc(sizeof(numero),1);
zero->bytes = 1;
zero->valor = calloc(zero->bytes,1);
zero->valor[0] = 0;
b = zero;
i = 0;
while(i< e) {
j = 0;
tofree = calloc(sizeof(numero*),10);
while(j < 10) {
t = add_numero(a,b);
tofree[j++] = t;
b = t;
}
free_numero(a);
a = copiar(b);
j = 0;
while(j<10) {
free_numero(tofree[j++]);
}
free(tofree);
b = zero;
i++;
}
free_numero(b);
return a;
}

numero *valor(char *n) {
numero *zero,*b;
numero **numeros;
char *ptr;
int bytes;
int i,j;
printf("procesando numero %s\n",n);
ptr = n;
bytes = strlen(n);
numeros = calloc(sizeof(numero*),bytes);
i = 0;
while(i < bytes) {
numeros[i] = valorBase10(ptr[i] - '0' , (bytes-1) - i);
//debug("numeros[i]",(unsigned char*)numeros[i],sizeof(numero));
//debug("%c x10^%i : numeros[%i]->valor",(unsigned char*)numeros[i]->valor,numeros[i]->bytes,ptr[i],(bytes-1) - i,i);
i++;
}
zero = calloc(sizeof(numero),1);
zero->bytes = 1;
zero->valor = calloc(zero->bytes,1);
zero->valor[0] = 0;
b = zero;
i = 0;
while(i < bytes) {
b = add_numero(numeros[i],b);
free_numero(numeros[i]);
i++;
}
//debug("b",(unsigned char*)b,sizeof(numero));
debug("b->valor",(unsigned char*)b->valor,b->bytes);
free(zero);
return b;
}
unsigned short add(unsigned char a, unsigned char b) {
return a+b;
}
int main() {
numero *n;
n = valor("1"); //Ejemplo de 1 solo digito
free_numero(n);
n = valor("50"); //Ejemplo de 2 digitos
free_numero(n);
n = valor("200"); //Ejemplo de 3 digitos
free_numero(n);
n = valor("255"); //Maximo numero de 1 byte
free_numero(n);
n = valor("65535"); //Maximo numero de 2 bytes
free_numero(n);
n = valor("4294967295"); //Maximo numero de 4 bytes
free_numero(n);
n = valor("18446744073709551615"); //Maximo numero de 8 bytes
free_numero(n);
n = valor("98765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210"); //Ejemplo de un Googol???
printf("el numero necesita %i bytes\n",n->bytes);
free_numero(n);
}