domingo, 22 de mayo de 2011

Factorial de números grandes

Hace poco estuve dictando un taller de C/C++ para ingresantes en la facultad como parte de las actividades que organiza la C.S.L. San Marcux.

En una de las clases, hicimos un ejemplo sencillo de cómo calcular el factorial de un número usando un bucle for. Sin embargo ese programa fallaba cuando el factorial de un número era demasiado grande, el valor no entraba en un entero de 4 bytes (int) y había un desbordamiento de memoria :(

Una mente inquieta me pregunto entonces ¿Como hacemos para que no falle? A lo que le respondí que debíamos hacer un artificio y enseñarle a la computadora a multiplicar con vectores. Sin embargo no llegué a programar ese algoritmo en clase por falta de tiempo y por que seguro todos volaban xD

Hace unos días me puse a programar ello así que publicaré el código aquí y quizá aquel que preguntó algún día lo encuentre googleando.

Fig. 1 - Calculo del factorial de 100.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 100

struct GranNumb {
 int *v;
 int n;
};

GranNumb granprod(GranNumb fact_1, GranNumb fact_2) {
 int *v, n;
 n = (fact_1.n > fact_2.n) ? 2*fact_1.n : 2*fact_2.n;
 v = new int[n];
 
 for(int i=0; i<n; i++) v[i] = 0;
 
 for(int i=0; i<fact_1.n; i++) {
  for(int j=0; j<fact_2.n; j++) {
   int prod = fact_1.v[i] * fact_2.v[j] + v[i+j];
   int u = prod % 10;
   int d = prod / 10;
   v[i+j] = u;
   v[i+j+1] += d;
  }
 }
 
 GranNumb gn;
 gn.n = 0;
 gn.v = v;
 
 for(int i=n-1; i>=0; i--) {
  if(v[i] != 0) {
   gn.n=i+1;
   break;
  }
 }
 
 return gn;
}

GranNumb grandec(GranNumb gn) {
 int *v = new int [gn.n];
 for(int i=0; i<gn.n; i++) v[i] = gn.v[i];
 
 if(gn.n == 0) {
  return gn;
 } else {
  for(int i=0; i<gn.n; i++) {
   if(v[i] == 0) {
    v[i] = 9;
   } else {
    v[i]--;
    break;
   }
  }
 }

 GranNumb dec;
 dec.n = 0;
 dec.v = v;
 for(int i=gn.n-1; i>=0; i--) {
  if(v[i] != 0) {
   dec.n=i+1;
   break;
  }
 }
 return dec;
}

GranNumb granfact(GranNumb gn) {
 if( gn.n == 0) {
  GranNumb uno;
  uno.n = 1;
  uno.v = new int[1];
  uno.v[0] = 1;
  return uno;
 } else {
  return granprod(gn, granfact(grandec(gn)));
 }
}

int main() {
 char s[MAX];
 
 printf("Ingresar N: ");
 scanf("%s", s);

 GranNumb gn;
 gn.n = strlen(s);
 gn.v = new int[gn.n];
 for(int i=0; i<gn.n; i++) gn.v[i] = (int)s[gn.n-1-i] - 48; //convierte caracter en cifra
 
 GranNumb fact = granfact(gn);
  
 for(int i=fact.n-1; i>=0; i--) {
  printf("%d", fact.v[i]);
 }
 printf("\n");
 
 return 0;
}

Saludos.

5 comentarios:

  1. xD entiendo la diferencia, decía "C/C++" por que tampoco es C++ puro y orientado a objetos.

    Un saludo, gracias.

    ResponderEliminar
  2. Ingrese un n·mero entero, cuyo factorial desea conocer
    250! =
    32328562609091077323208145520243684709948437176737806667479424271128237475551112
    09488817915371028199450928507353189432926730931712808990822791030279071281921676
    52724018926473321804118626100683292536513367893908956993571353017504051317876007
    72479330654023390061648255522488194365725860573992226412548329822048491377217766
    50641276858807153128978777672951913990844377478702589172973255150283241787320658
    18848206247858265980884882554880000000000000000000000000000000000000000000000000
    0000000000000

    ResponderEliminar
  3. Los modelos probalísticos son básicamente tres:
    El de Bernoulli
    El de Poisson
    y el de Gauss. El de Poisson y de Gauss son aproximaciones del Modelo probabilístico de Bernoulli o Binomial. El problema para usar éste modelo es calcular los números combinatorios y por ende los factoriales, que como lo mostré más adelante son muy grandes; sin embargo ahora no debiera ser ningún problema. propongo que se use sólo el modelo probabilístico binomial para diversas aplicaciones.
    saludos.

    ResponderEliminar
  4. Interesante tu solución pero tiene una complejidad O(n*2) en el peor de los casos, con la programación funcional lo harías en 3 lineas, aunque aun así hubieran volado los chicos (cachimbos). Buen post

    factorial 0 = 1
    factorial n = n * factorial (n - 1)

    main = print $ factorial 100

    ResponderEliminar