Factorial hasta 1000

[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

[[seoane]]

Bueno, el factorial de 1000 tiene 2.568 cifras 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 :

Código Delphi [-]
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 ...

402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000


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 ...

402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

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]]

Empezado por 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

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

[[seoane]]

Buena idea dec, ¿alguno tiene uno de esos procesadores de doble núcleo y un montón de Mhz? 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, 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) ¿Puede considerarse como una religión, o acaso me debo conformar con la religión de los simpson?

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

[[ArdiIIa]]

Empezado por seoane

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

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


Ver Imagen: factorial1pz28z6.jpg

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

[[xEsk]]

Empezado por seoane

Buena idea dec, ¿alguno tiene uno de esos procesadores de doble núcleo y un montón de Mhz? 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 ...

402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

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]]

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

Empezado por Robert01

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 ...