Foro de elhacker.net

Pues eso.

¿Como defino en C un tipo bigint o similar que admita números grandes? ¿hay alguna librería? ¿como se hace?

Existe un tipo de dato llamado long int o simplemente long (que ocupa 4 bytes) y, cuando es signado va desde el -2147483648 hasta el 2147483647 y cuando no es signado va desde el 0 hasta el 4294967295.

Hombre claro que los long son mayores que los int pero eso no son big int. Un big int puede tener 200 dígitos.

Estoy trabajando en unos test de primalidad (miller-rabin) y no tengo problema con números muy pequeños pero con números de dos o tres cifras ya no puedo. Lo correcto sería trabajar con números de mínimo veinte cifras osea que el long no vale ni de coña. Intenta calcular 50^100 o 60! o cualquier cosa asi con el tipo long.

Yo creo que hay alguna librería que se incluye y que tiene funciones para eso pero no se donde encontrarla ni nada. Por eso pregunto.

Un saludo

En vez de trabajar con enteros, quizá podrías probar con doubles, (o long doubles). No son tipos puramente de enteros, pero su rango de representación abarca números mayores.

Sin embargo, esto te puede acarrear que algunos de tus números no sean representables por la propia naturaleza del formato en coma flotante y tengas problemas de redondeo.

Efectivamente tal como dices no es posible utilizar coma flotante y de hecho aún así habría un límite (mayor pero límite) que lo hace inviable. Podría ocurrir que pudieras calcular 50! y no pudieras 51! por ejemplo. La naturaleza de big int es "cualquier tamaño" y lo que si puede pasar es que según la cpu que tengas la operación pueda llevar mas o menos tiempo.

En google veo que algunos códigos hacen un include "bigint.h" y a partir de ahí ya se puede trabajar con ese tipo de números, pero no consigo información de donde obtenerlo.

Un saludo

Jeje te gusto lo de criptografía :P
¿Probaste este (http://cs.nyu.edu/exact/core/download/core_v1.6/html/BigInt_8h-source.html)?

Saludos y ya me cuentas como te fue (no puedo probarlo ahora, por eso te lo pregunto).
;)

Eso si es lo que busco o al menos lo parece (a falta de pruebas)
 ;D

He mirado eso de gmp.h y creo que la cosa pasa por instalar los paquetes libgmp-ocaml y libgmp3c2 (en debian).

Esto si parece ser lo que buscaba.

Si que me gustó la criptografía. Es una ciencia aparte y un nuevo reto je je je. Igual me ha pasado con Gambas como lenguaje de programación para sustituir a VB y en entornos linux. Disfruto con ello.

Muchas gracias
 ;D

Lh: No hagas doble post, utiliza el botón modificar.

Ya lo he solucionado. Ahora que lo veo no es tna dificil pero ha habido un rato que no enteraba por donde me venían las cosas.

Primero para instalarlo hay que instalar los paquetes libgmp3c2 y libgmp3-devel.

Una vez instalado hay que conocer las funciones que incluye para trabajo con bignum. La documentación de esas funciones está aquí

http://gmplib.org/manual/index.html#Top (http://gmplib.org/manual/index.html#Top)

Y mas concretamente las funciones correspondientes están aquí
http://gmplib.org/manual/Function-Classes.html#Function-Classes (http://gmplib.org/manual/Function-Classes.html#Function-Classes)

Y ahora pongo un ejemplo de crear un número grande y hacer una suma con él. Luego se muestra en pantalla.


Primero inicializo x, y y z. Luego asigno a x un valor que especifico que está en base 10. Asigno a y el valor 1 y especifico que está en base 10. Luego sumo x e y y dejo el resultado en z que hasta ese momento valía cero. Por último saco por stdout el valor de z.

Muchas gracias
 ;D

[editado]
Olvidé decir que para compilarlo hay que incluir obligatoriamente la librería gmp o no funcionará.
Es decir pra compilar la anterior aplicación y que funcione habrá que hacerlo así
gcc prueba.c -lgmp -o prueba

[/editado]

Aclaración :

@E.P.I:  Estás describiendo el int ... un long en condiciones normales es de 64 bits, no 32  ..
2^32 = 4,294,967,296 (si no, le sacás un bit para el signo)

Saludos.

Lo que expuso Horricreu es correcto ya que no se refiere al máximo de posibilidades si no al rango comprendido.


es perfectamente correcto.
En cuanto a los bytes, el requerimiento mínimo de un long es de 4 bytes, y de ahí para arriba puede variar dependiendo la plataforma y la arquitectura en la que estemos trabajando.
long long en todo caso si requiere como mínimo 64bits, pero esa es otra historia ya que esto no se ha mencionado aquí.

Saludos

Cierto, fail mío, me confundí con el tema de la arquitectura (en 64 bits automáticamente es 8 bytes), cierto que en 32 es 4 ...

Saludos.

No exactamente, no depende solo de la arquitectura, también depende del modelo de datos utilizado en la plataforma y del entorno de desarrollo.
Por ejemplo, en la mayoría de Unix,Unix-like de arquitectura 64bits, el requerimiento mínimo de un long es 4 bytes, sin embargo un long y un long long tienen 8 bytes. Por otro lado, en un Windows/NT de arquitectura 64bits, un long tiene 4 bytes y un long long tiene 8.
El requerimiento mínimo de 8 bytes si aplica para los enteros long long u por ejemplo para los punteros, pero no para los enteros long.

Saludos.

El bigint no es estandar, si no me equivoco  :-\.

Tengo entendido que si tienes que trabajar con numero muy grandes que superan a los limites de los tipos basicos, se puede trabajar con cadenas ( strings ), y despues "simular" las operaciones matematicas.

Me equivoco? , es mejor usar el bigint, aunque no sea estandar?

Saludos!

WaRc3L

Efectivamente no es estandar pero a veces es necesario y en absoluto veo que las operaciones que podrías necesitar con números grandes puedan resolverse con strings.

Bueno, poder poder lo que es poder seguramente se podrá (de hecho esas funciones de alguna forma se computan) pero intenta calcular un número de cincuenta dígitos elevado a uno de 100 a base de strings por ejemplo.

No son casos habituales pero tampoco son extremadamente raros. Por ejemplo seguramente si excedes 20! ya estas sobrepasando los tipos comunes. Que la gente habitualmente no anda calculando 50^50 o 50! estoy de acuerdo, pero creo que en diversas actividades es bastante probable encontrarse con ese tipo de problemas.

Un saludo
 ;D

En efecto, como ejemplo el siguiente programa

/* Reto #18: Calcular el factorial de n, 0<=n<=100 */
 
#include <stdio.h>
#include <string.h>
 
#define MAX_LON_FACT 2600  /* suficiente para calcular el factorial de 1000 */
 
#define CharADig(c) ((int)((c)-'0'))
#define DigAChar(d) ((char)(d)+'0')
 
void mulenterolargo(int q,char *z)
{
  int temp=0,i,ltemp,lz=strlen(z);
  char stemp[15];
 
  for(i=lz-1;i>=0;i--)
  {
    temp+=CharADig(z[i])*q;
    z[i]=DigAChar(temp%10);
    temp/=10;
  }
 
  if(temp)
  {
    ltemp=sprintf(stemp,"%d",temp);
    memmove(&z[ltemp],&z[0],lz+1);
    memcpy(&z[0],stemp,ltemp);
  }
}
 
const char *factorial(int n,char fact[])
{
  int i;
  strcpy(fact,"1");
  for(i=2;i<=n;i++)
    mulenterolargo(i,fact);
  return fact;
}
 
int main(void)
{
  char fact[MAX_LON_FACT+1];
  int n;
 
  printf("Digite el n£mero: ");
 
  if(scanf("%d",&n)!=1 || n<0 || n>1000)
    return 1;
 
  printf("\n%d! = %s\n\n",n,factorial(n,fact));
  printf("Longitud = %d d¡gitos\n",strlen(fact));
  return 0;
}
 

Saludos!

Bien, pues tu usa eso si te hace feliz.

Yo usaré gmp que trabaja con esos valores directamente en binario y me hace feliz a mi.

Aparte de que si miras ese código verás o que está incompleto o no funciona. A mi me da igual porque no pienso usarlo je je je pero bueno. Aun suponiendo que funcionara ¿echamos una carrera a ver quien resuelve antes 894689038903^766656565656565 mod 8949083489008989090309

Porque en gmp eso es

 ;D

P.D.
Que no te suene que me rio de ti o algo. Nada mas lejos. Solo tengo interes en la gente que está aprendiendo C que vea las posibilidades de esto para superar los límites naturales de C. Nada mas que eso. Por eso me he extendido en la respuesta.

Un saludo

Ok, no te molestes  ;D. Sin duda alguna será mejor usar una biblicoteca de funciones especializada en el manejo de números grandes para hacer el trabajo que estes haciendo.

Saludos.