La magia del Smalltalk: Capítulo 3 - ¿Cuanto? ¿Facto qué?
¿Tienen una idea del pedazo de número que es el factorial de 1000?
Uhhh, perdón... Primero lo primero: ¿Tienen una idea que es el factorial? :-)
Rápidamente les recuerdo que el factorial de un número N
n! = 1 × 2 × 3 × ... × (n-1) × n
El factorial de 0, por convención, es 1. El factorial de 1 es 1, el factorial de 2 es 1x2, el factorial de 3 es 1x2x3, el factorial de 4 es 1x2x3x4, etc.
Ahora pensemos un segundo: ¿Cuanto será el factorial de 1000? Es un número monstruoso de grande. Usemos nuestro Smalltalk para experimentar un poco.
| 1000 factorial. |
El factorial de 1000 es, según mi squeak:
| 402387260077093773543702433923003985719374864210714632543799910429938 512398629020592044208486969404800479988610197196058631666872994808558 901323829669944590997424504087073759918823627727188732519779505950995 276120874975462497043601418278094646496291056393887437886487337119181 045825783647849977012476632889835955735432513185323958463075557409114 262417474349347553428646576611667797396668820291207379143853719588249 808126867838374559731746136085379534524221586593201928090878297308431 392844403281231558611036976801357304216168747609675871348312025478589 320767169132448426236131412508780208000261683151027341827977704784635 868170164365024153691398281264810213092761244896359928705114964975419 909342221566832572080821333186116811553615836546984046708975602900950 537616475847728421889679646244945160765353408198901385442487984959953 319101723355556602139450399736280750137837615307127761926849034352625 200015888535147331611702103968175921510907788019393178114194545257223 865541461062892187960223838971476088506276862967146674697562911234082 439208160153780889893964518263243671616762179168909779911903754031274 622289988005195444414282012187361745992642956581746628302955570299024 324153181617210465832036786906117260158783520751516284225540265170483 304226143974286933061690897968482590125458327168226458066526769958652 682272807075781391858178889652208164348344825993266043367660176999612 831860788386150279465955131156552036093988180612138558600301435694527 224206344631797460594682573103790084024432438465657245014402821885252 470935190620929023136493273497565513958720559654228749774011413346962 715422845862377387538230483865688976461927383814900140767310446640259 899490222221765904339901886018566526485061799702356193897017860040811 889729918311021171229845901641921068884387121855646124960798722908519 296819372388642614839657382291123125024186649353143970137428531926649 875337218940694281434118520158014123344828015051399694290153483077644 569099073152433278288269864602789864321139083506217095002597389863554 277196742822248757586765752344220207573630569498825087968928162753848 863396909959826280956121450994871701244516461260379029309120889086942 028510640182154399457156805941872748998094254742173582401063677404595 741785160829230135358081840096996372524230560855903700624271243416909 004153690105933983835777939410970027753472000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000 000000000000000 |
Ufff... voy a tener que confiar en Squeak y creerle que ese número es el resultado. Para validar un poco la respuesta, voy a usar algo del poco conocimiento que me dio la escuela secundaria, y voy a usar la propiedad de los factoriales que dice que:
N! / (N-1)! = N
Entonces evaluamos en Smalltalk:
| 1000 factorial / 999 factorial. |
Y con un poquito de suerte nos debería contestar 1000.
Volviendo al número monstruoso anterior: creo que no hace falta aclarar que ese número no cabe en un entero ni de 16, ni de 32, ni de 64 bits. Para el manejo de enteros tenemos 3 clases:
SmallInteger: para enteros que entren en 31 bits.
LargePositiveInteger: para enteros positivos que no entren en 30 bits.
LargeNegativeInteger: como la anterior, pero para negativos.
Todas tienen como superclase a Integer, que es la clase abstracta para todas las implementaciones de enteros. Justamente en Integer es donde encontramos la implementación de #factorial. Es decir: el algoritmo para calcular factoriales de número chicos, o de número grandes, es el mismo.
Algunos ejercicios más con factoriales:
¿Cuántos dígitos tiene el factorial de 1000?
1000 factorial asString size -> 2568
¿Cuánto tiempo tarda mi Squeak en calcular el factorial de 1000?
Time millisecondsToRun: [1000 factorial] -> 12
Sí, es verdad, el factorial de 1000 tarda en calcular 12 milisegundos en mi máquina... Si no lo creen, prueben ustedes mismos.
¿Cuánto tiempo tarda en calcular el factorial de 1000 el lenguaje de programación que están usando?
publicado por Diego Gomez Deck @ 13:50
6 comentarios
6 Comentarios:
Una curiosidad, en mi viejo (y Noble) Pentium III con 256 MB de RAM, los tiempos necesarios para ejecutar:
Time millisecondsToRun: [1000 factorial]
son:
con Squeak 3.8: 30 segundos.
con Dolphin 5.1.4: 9 segundos.
¿Por qué Dolphin lo hace más rápido?
Saludos.
Me imagino que será porque Dolphin tiene una implementación NO-recursiva del algoritmo del factorial.
Casualmente acabo de cambiar a mi viejito y noble Pentium III por un Celeron 2.66GHz con 512 MB de RAM y los tiempos que obtengo ahora han bajado increiblemente:
Squeak: 7 segundos
Dolphin: 2 segundos
Francamente impresionante.
Y en java existe esa funcion?
Pueden contestarme a jameraguilar@gmail.com, es que ando desesperado intentando conseguir el factorial de un número grande.
Gracias
en JAVA puedes tomar el tiempo antes de empezar y despues de terminar la sentencia de factorial, asi sabras cuanto demora. Ahora si preguntas por una funcion q calcule el factorial - No lo se - pero puedes hacerla tu mismo, es simple... la duda q tengo, es q la recursividad deberia tomar menos tiempo, y no como dice Diego.
Saludos.
Es curioso lo que dicen sobre el factorial, se que esto ya tiene tiempo que lo sacaron, yo programo en lenguaje c y mi codigo que calcula el factorial de un numero tardo:
real 0m0.064s
user 0m0.028s
sys 0m0.004s
y sobre lo que hablan de la funcion de recurrencia no hay necesidad de hacerla, mi idea es sencilla manejo arreglos de enteros, cada posicion de mi arreglo forma parte de mi numero, nada mas que yo divido al numero en partes iguales.
Publicar un comentario
<< Principal