Factorial hasta 1000

[Cheswar]

Alguien me podria ayudar, necesito saber como puedo hacer factorial hasta n numeros, su limite es 1000, y no se si hay algun tipo de variable que tenga capacidad para un numero tan grande como el factorial de 1000.
Les agradezco.:D

[Robert01]

Hola

Podrías usar una variable de tipo extended:

Extended: 3.4 x 10^-4932 a 1.1 x 10^4932.

Creo que el factorial de 1000 es menor que 1.1 x 10^4932.

Saludos

[Robert01]

Hola

procedure TForm1.Button1Click(Sender: TObject);
var
i: Integer;
Num: extended;
Numt:extended;
begin
Num:=1;
for i:=1 to 1000 do begin
Num:=Num*i;
end;
Edit1.Text:=FloatToStr(num);

end;

El factorial de 1000 es = 4,02387260077094 E2567

Saludos

[Cheswar]

Te agradezco la ayuda, no estaba seguro del tipo de variable que necesitaba, pero gracias ya lo probe y funciona bien.:D:D:D

[seoane]

Bueno, el factorial de 1000 tiene 2.568 cifras :eek: Lamento decir que no existe (al menos no conozco) ninguna variable numérica de delphi que soporte ese numero de cifras. Así que toca hacerlo "a mano", para esto vamos a echar mano de los números "SuperLargos" que ya describir en algún otro hilo. No es la forma mas eficiente de hacerlo, pero funciona :D :

program Calcular;

{$APPTYPE CONSOLE}

uses
SysUtils;

const
Max = 2600;

type
TSuperLargo = array[0..Max] of Byte;

function AddSuper(a,b: TSuperLargo; Acarreo: Integer): TSuperLargo; overload;
var
i,j: integer;
begin
for i := 0 to Max do
begin
j:= (Integer(a[i]) + Integer(b[i])) + Acarreo;
Result[i]:= j mod 10;
Acarreo:= j div 10;
end;
end;

function AddSuper(a,b: TSuperLargo): TSuperLargo; overload;
begin
Result:= AddSuper(a,b,0);
end;

function IncSuper(a: TSuperLargo; Acarreo: Integer): TSuperLargo; overload;
var
i,j: integer;
begin
for i := 0 to Max do
begin
j:= Integer(a[i]) + Acarreo;
Result[i]:= j mod 10;
Acarreo:= j div 10;
end;
end;

function MulSuper(a: TSuperLargo; b: Byte): TSuperLargo; overload;
var
i,j: integer;
Acarreo: Integer;
begin
Acarreo:= 0;
for i := 0 to Max do
begin
j:= (Integer(a[i]) * Integer(b)) + Acarreo;
Result[i]:= j mod 256;
Acarreo:= j div 256;
end;
end;

function ShiftLSuper(a: TSuperLargo): TSuperLargo;
var
i: integer;
begin
Result[0]:= 0;
for i:= 0 to Max - 1 do
Result[i+1]:= a[i];
end;

function ShiftRSuper(a: TSuperLargo): TSuperLargo;
var
i: integer;
begin
Result[Max]:= 0;
for i:= 1 to Max do
Result[i-1]:= a[i];
end;

function MulSuper(a,b: TSuperLargo): TSuperLargo; overload;
var
i: integer;
begin
FillChar(Result,Sizeof(Result),0);
for i:= Max downto 0 do
begin
Result:= ShiftLSuper(Result);
Result:= AddSuper(Result,MulSuper(a,b[i]));
end;
end;

function SuperToStr(a: TSuperLargo): string;
var
i: integer;
flag: Boolean;
begin
Result:= '';
flag:= FALSE;
for i := Max downto 0 do
begin
if flag then
Result:= Result + IntToStr(a[i])
else if a[i] > 0 then
begin
flag:= TRUE;
Result:= Result + IntToStr(a[i]);
end;
end;
end;

function Factorial(i: int64): String;
var
a,b: TSuperLargo;
j: Integer;
begin
FillChar(a,Sizeof(a),#0);
FillChar(b,Sizeof(b),#0);
a[0]:= 1;
b[0]:= 1;
for j:= 2 to i do
begin
b:= incSuper(b,1);
a:= MulSuper(a,b);
end;
Result:= SuperToStr(a);
end;

var
Marca: TDateTime;
begin
Writeln('Calculando el factorial de 1000 ...');
Writeln;
Marca:= Now;
Writeln(Factorial(1000));
Writeln;
Writeln;
Writeln('Se empleo en el calculo un tiempo de: ' + TimeToStr(Now-Marca));
end.

Aunque es mejor que te lo tomes con tranquilidad, en mi equipo tardo 8 minutos y 21 segundos en calcular el factorial de 1000.

Por si alguien tiene curiosidad, esta es la salida del programa:

Calculando el factorial de 1000 ...

4023872600770937735437024339230039857193748642107146325437999104299385123986290205920442084869694048 0047998861019719605863166687299480855890132382966994459099742450408707375991882362772718873251977950 5950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476 6328898359557354325131853239584630755574091142624174743493475534286465766116677973966688202912073791 4385371958824980812686783837455973174613608537953452422158659320192809087829730843139284440328123155 8611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151 0273418279777047846358681701643650241536913982812648102130927612448963599287051149649754199093422215 6683257208082133318611681155361583654698404670897560290095053761647584772842188967964624494516076535 3408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200 0158885351473316117021039681759215109077880193931781141945452572238655414610628921879602238389714760 8850627686296714667469756291123408243920816015378088989396451826324367161676217916890977991190375403 1274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786 9061172601587835207515162842255402651704833042261439742869330616908979684825901254583271682264580665 2676995865268227280707578139185817888965220816434834482599326604336766017699961283186078838615027946 5955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657 2450144028218852524709351906209290231364932734975655139587205596542287497740114133469627154228458623 7738753823048386568897646192738381490014076731044664025989949022222176590433990188601856652648506179 9702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819 3723886426148396573822911231250241866493531439701374285319266498753372189406942814341185201580141233 4482801505139969429015348307764456909907315243327828826986460278986432113908350621709500259738986355 4277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994 8717012445164612603790293091208890869420285106401821543994571568059418727489980942547421735824010636 7740459574178516082923013535808184009699637252423056085590370062427124341690900415369010593398383577 7939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000


Se empleo en el calculo un tiempo de: 0:08:21

[Robert01]

Hay una forma aproximada de calcular el factorial de un número muy grande, es a través de la fórmula de Sterling:

N! := Sqr(2 * PI * N) * (N / E) ^ N

Saludos

[dec]

Hola,

Yo no he dejado de hacer otras cosillas y bueno...


Calculando el factorial de 1000 ...

4023872600770937735437024339230039857193748642107146325437999104299385123986290205920442084869694048 0047998861019719605863166687299480855890132382966994459099742450408707375991882362772718873251977950 5950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476 6328898359557354325131853239584630755574091142624174743493475534286465766116677973966688202912073791 4385371958824980812686783837455973174613608537953452422158659320192809087829730843139284440328123155 8611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151 0273418279777047846358681701643650241536913982812648102130927612448963599287051149649754199093422215 6683257208082133318611681155361583654698404670897560290095053761647584772842188967964624494516076535 3408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200 0158885351473316117021039681759215109077880193931781141945452572238655414610628921879602238389714760 8850627686296714667469756291123408243920816015378088989396451826324367161676217916890977991190375403 1274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786 9061172601587835207515162842255402651704833042261439742869330616908979684825901254583271682264580665 2676995865268227280707578139185817888965220816434834482599326604336766017699961283186078838615027946 5955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657 2450144028218852524709351906209290231364932734975655139587205596542287497740114133469627154228458623 7738753823048386568897646192738381490014076731044664025989949022222176590433990188601856652648506179 9702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819 3723886426148396573822911231250241866493531439701374285319266498753372189406942814341185201580141233 4482801505139969429015348307764456909907315243327828826986460278986432113908350621709500259738986355 4277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994 8717012445164612603790293091208890869420285106401821543994571568059418727489980942547421735824010636 7740459574178516082923013535808184009699637252423056085590370062427124341690900415369010593398383577 7939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000

Se empleo en el calculo un tiempo de: 0:14:22


AMD Athlon a 1000 Mhz y 768 MB de RAM en un Windows XP SP2

[seoane]

Hay una forma aproximada de calcular el factorial de un número muy grande, es a través de la fórmula de Sterling

¿No te gusto la mia? El de 1000 lo clava :D

[seoane]

Buena idea dec, ¿alguno tiene uno de esos procesadores de doble núcleo y un montón de Mhz? :D Lo digo por comparar ...

[Robert01]

Me gustó, es un muy buen código.

Mañana lo voy a probar en freepascal bajo ubuntu a ver cuanto tarda, de ese modo vamos a compara linux vs windows.

Saludos

[Delphius]

Pues yo obtuve este resultado: 0:11:15

En un AMD Duron de 1,16 Ghz, RAM: 480 Mb, Window$ XP Profesional versión 2002 (5.1) SP2

Esto me hace recordar a algunas comparaciones de algoritmia que hacía de cuando era joven:p:D, snif... ¡que recuerdos aquellos! Y ahora que hago memoria... es posible que nunca vuelva a recuperar el libro (original. No copia) de Estructuras de datos y algoritmos... no debí haberlo prestado. Justo cuando lo necesito para repasar algunas cosas que no recuerdo y no tomé apunte:( (menos mal que existe San Google:D) ¿Puede considerarse como una religión, o acaso me debo conformar con la religión de los simpson:D?

Saludos,
PD: No se porque pero que me dieron cuerda... soy una máquina de decir... pe.......:p

[seoane]

Voy a dar ejemplo y poner mis resultados.

En un AthlonXP 2600 / 512MB de RAM / Ubuntu 7.04 / Wine 0.9.33
-- > 07:08

En un AthlonXP 1800 / 512 de RAM / WindowsXP SP2
--> 08:14

Era de esperar que en el ordenador mas rápido el calculo se terminara antes, lo que no era tan previsible es que ejecutando el programa sobre linux con la ayuda de wine se obtuviera un resultado tan bueno. Que cada uno saque sus conclusiones ....

[Robert01]

Tengo un pequeño problema: cuando ejecuto el programa no me da el tiempo empleado sino un número con formato de hora, por ejemplo 12:05:34 am

No se que es lo que anda mal porque yo no toqué para nada el código

[seoane]

El timepo se calcula como la diferencia entre do TDateTime:

TimeToStr(Now-Marca)

El resultado de esta operación también es un TDateTime. El problema puede ser al convertir esa variable a texto, seguramente por la configuración de la hora en tu equipo este interpretando lo que debería ser "05:34" como "12:05:34".

¿Que equipo tienes? ¿05:34 te parece que es el tiempo que mas o menos le llevo?

[seoane]

Acabo de comprobar que como ya advertía no es la forma mas eficiente de hacerlo, por ejemplo en python, un script tan sencillo como este:

a=1
for i in range(1000):
a=a*(i+1)

print a

Devuelve el factorial de forma inmediata, sin necesidad de esperar :(

[ArdiIIa]

Buena idea dec, ¿alguno tiene uno de esos procesadores de doble núcleo y un montón de Mhz? :D Lo digo por comparar ...

Se empleo en el calculo un tiempo de 0:02:10


Ver Imagen: factorial1pz28z6.jpg (http://www.imaxenes.com/imagen/factorial1pz28z6.jpg.html)


Intel(R) Core(TM) 2 CPU
6600 @ 2.40 GHz
4 GB RAM

[Robert01]

Acabo de comprobar que como ya advertía no es la forma mas eficiente de hacerlo, por ejemplo en python, un script tan sencillo como este:

a=1
for i in range(1000):
a=a*(i+1)

print a
Devuelve el factorial de forma inmediata, sin necesidad de esperar :(

Es similar al código que yo puse al principio y además es mucho más rápido.

En mi compu tu código se ejecuta en 5:25 bajo windows, es una máquina con micro intel em64t 3.08 Ghz con 512 mb de Ram.

[xEsk]

Buena idea dec, ¿alguno tiene uno de esos procesadores de doble núcleo y un montón de Mhz? :D Lo digo por comparar ...

Hola, he probado el programa a ver mis resultados, la primera vez he sido un tontolaba lo he probado dandole doble click al programa, pero como era de esperar se ha cerrado nada mas terminar y no pude ver nada xDDD

La segunda vez, este ha sido el resultado:

Calculando el factorial de 1000 ...

4023872600770937735437024339230039857193748642107146325437999104299385123986290205920442084869694048 0047998861019719605863166687299480855890132382966994459099742450408707375991882362772718873251977950 5950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476 6328898359557354325131853239584630755574091142624174743493475534286465766116677973966688202912073791 4385371958824980812686783837455973174613608537953452422158659320192809087829730843139284440328123155 8611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151 0273418279777047846358681701643650241536913982812648102130927612448963599287051149649754199093422215 6683257208082133318611681155361583654698404670897560290095053761647584772842188967964624494516076535 3408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200 0158885351473316117021039681759215109077880193931781141945452572238655414610628921879602238389714760 8850627686296714667469756291123408243920816015378088989396451826324367161676217916890977991190375403 1274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786 9061172601587835207515162842255402651704833042261439742869330616908979684825901254583271682264580665 2676995865268227280707578139185817888965220816434834482599326604336766017699961283186078838615027946 5955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657 2450144028218852524709351906209290231364932734975655139587205596542287497740114133469627154228458623 7738753823048386568897646192738381490014076731044664025989949022222176590433990188601856652648506179 9702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819 3723886426148396573822911231250241866493531439701374285319266498753372189406942814341185201580141233 4482801505139969429015348307764456909907315243327828826986460278986432113908350621709500259738986355 4277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994 8717012445164612603790293091208890869420285106401821543994571568059418727489980942547421735824010636 7740459574178516082923013535808184009699637252423056085590370062427124341690900415369010593398383577 7939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000

Se empleo en el calculo un tiempo de: 0:05:19

Lo he probado en un AMD Athlon 64 X2 Dual Core Processor 3800+, no es de los mas potentes ni mucho menos, pero... xDDDDD
Mientras el programa estaba funcionando yo iba haciendo cosas, pero no creo que afecte mucho, pq solo uno de los procesadores estaba trabajando al 100% (50% del total).

Saludos.

[seoane]

:eek: La leche, de donde sacáis tremendos equipos. El mio parece un ábaco al lado de los vuestros :(


Es similar al código que yo puse al principio y además es mucho más rápido.

La diferencia es que python te devuelve las 2.568 cifras exactas, nada de aproximaciones. En cambio si utilizas un extended en delphi, es verdad que el calculo es rápido pero solo obtienes una aproximación, ya que solo te devuelve las 15 primeras cifras.

Se me hace raro que delphi no pueda manejar números tan grandes. En otra ocasión el amigo Roman nos hablo del tipo TBCD, pero ni siquiera el soporta 1000 cifras. ¿Alguien conoce algún algoritmo eficiente de multiplicación para números grandes? Solo por curiosidad ...

[seoane]

Bueno, alguien que crea un programa para no tener que resolver los sudokus (http://delphi.jmrds.com/?q=node/19) a mano :D, no podía contentarse con el algoritmo anterior.

Así que considerando que que 1000, incluso 10000, nos cabe dentro de una variable de tipo integer, podemos optimizar "un poco" el algoritmo de multiplicación.

program Fast;

{$APPTYPE CONSOLE}

uses
SysUtils, Windows;

const
Lon = 2600;
type
TSuperLargo = array[0..Lon] of Byte;

function MulSuper(A: TSuperLargo; B: Integer): TSuperLargo;
var
i,j: integer;
Ac, Desp, Dig: Integer;
begin
Desp:= 0;
FillChar(Result,Sizeof(Result),#0);
while B > 0 do
begin
Dig:= B mod 10;
B:= B div 10;
Ac:= 0;
for i:= 0 to Lon - Desp do
begin
j:= Integer(Result[i+Desp]) + (Integer(A[i]) * dig) + Ac;
Result[i+Desp]:= j mod 10;
Ac:= j div 10;
end;
inc(Desp);
end;
end;

function SuperToStr(a: TSuperLargo): string;
var
i: integer;
flag: Boolean;
begin
Result:= '';
flag:= FALSE;
for i := Lon downto 0 do
begin
if flag then
Result:= Result + IntToStr(a[i])
else if a[i] > 0 then
begin
flag:= TRUE;
Result:= Result + IntToStr(a[i]);
end;
end;
end;

function Factorial(i: integer): String;
var
j: Integer;
A: TSuperLargo;
begin
FillChar(A,Sizeof(A),#0);
A[0]:= 1;
for j:= 2 to i do
begin
A:= MulSuper(A,j);
end;
Result:= SuperToStr(a);
end;

var
Cont1, Cont2: int64;
Frec: int64;
begin
Writeln('Calculando el factorial de 1000 ...');
Writeln;
QueryPerformanceFrequency(Frec);
QueryPerformanceCounter(Cont1);
Writeln(Factorial(1000));
QueryPerformanceCounter(Cont2);
Writeln;
Writeln;
Writeln(Format('Se emplearon %d milisegundos',[((Cont2-Cont1) * 1000) div Frec]));
end.


La nueva marca es de tan solo 589 milisegundos :eek:

Que a gusto me he quedado :p :D

Edito:
El factorial de 10,000 (35,659 cifras) tarda 67,202 milisegundos, poco mas de un minuto.

Si alguien tiene curiosidad de saber cual es que se baje el adjunto :D

[ArdiIIa]

Se emplearon 106 milisegundos....

[seoane]

Se emplearon 106 milisegundos....

Vaya, casi 5 veces mas rápido tu equipo que el mio :( ¿sera hora de renovarme?

[ArdiIIa]

Vaya, casi 5 veces mas rápido tu equipo que el mio :( ¿sera hora de renovarme?

Es que soy seguidor de Alonso....:D

[seoane]

Es que soy seguidor de Alonso....:D

Tu lo que eres es un presumido :p ... (como Alonso :D)

[Robert01]

Estas son mis marcas:

fact 1000 = 285 miliseg

fact 10000 = 2334 miliseg

fact 100000 = 27239 miliseg

En windows, no he probado usarlo con wine en ubuntu al programa Fast.

Yo quise probar en freepascal pero hay algo que no anda bien, un error que dice que Result[i] es desconocida, tal vez alguna librería que no agregué.

Saludos

[Delphius]

Es que soy seguidor de Alonso....:D

Y yo del tortugo Ignacio:D (Bueno... creo que se llamaba asi)

Menos mal que no probé la versión en mi anterior "fitito": un Pentium con 333 Mhz, 128 Mb RAM y Windows 2000:eek::p

Tendría que ver, por cuiosidad, lo que hay en el archivo adjunto y probarlo. Después si me da la cabeza le hago un analisis de complejidad... ¡Lo que uno hace para salir y evitar las obligaciones!;):D

EDITO:
Lei mal... pensaba que en el archivo adjunto estaba el código para probar :p ... Un pequeño error de lectura. Pues que es un número grande...

Saludos,

[Delphius]

Bueno, y volviendo al tema original del hilo.
Creo que el amigo Cheswar (http://www.clubdelphi.com/foros/member.php?u=21371) ya eliminó su duda.

Aunque me llama la atención la necesidad de generar el factorial de números tan grandes. Un tema que ya fue ampliamente estudiado hace años...

No se cual será su objetivo, por lo general se deja estos tipos de ejercicios: factoriales, recursividad, numeros primos, capicuas... como inicio en la programación. Me cuesta capturar el sentido práctico, como programación, el hallar un número tan grande. Si tiene sentido en cambio si se quiere hacer un estudio de algoritmos... aunque como dije ya fue discutido hace tiempo.

De cualquier manera, Cheswar se ha llevado ya las respuestas.

Este post ha sido escrito no con la finalidad de tirar malas impresiones, sino como un intento de volver a canalizar los objetivos iniciales del hilo.
En un rato podría volver con el estudio de los algoritmos. Haciendo una comparación entre la versión lenta y rápida. Si es que le sirve de sustento a Cheswar (y claro... si el está de acuerdo e interesado).

Saludos,

[Robert01]

Pido disculpas por los resultados para factorial de 10000 y de 100000. ¡Son valores erróneos! no se en que estaba pensando cuando puse eso.

Saludos

[seoane]

Yo quise probar en freepascal pero hay algo que no anda bien, un error que dice que Result[i] es desconocida, tal vez alguna librería que no agregué.

En freepascal para devolver el valor en las funciones se utiliza el estilo clásico de pascal, es decir el propio nombre de la función. Así que prueba a utilizar MulSuper[i] en vez de Result[i], no lo he probado pero creo que debería de funcionar.


Pido disculpas por los resultados para factorial de 10000 y de 100000. ¡Son valores erróneos! no se en que estaba pensando cuando puse eso.

Si no me equivoco el de 100,000 correspondería a 10,000, y el de 10,000 a 1,000, serian ya unos tiempos razonables. El factorial de 100,000 no se puede calcular con este método porque se provoca un desbordamiento de la pila.

[xander]

En mi equipo el código expuesto por Seoane tal cual está se tarda 450 milisegundos en ejecutarse compilado en Delphi 2007, pero si le agrego a los procedimientos la sentencia inline se tarda solo 196 milisegundos!!!

En uno de esos equipos de doble nucleo que traen hasta aeromozas incluidas debe ser un tiro usando inline