Calculo de fatorial
bom dia a todos,
tenho duas funcoes pra calculo de fatorial sendo uma delas com chamada recursiva a propria funcao. o problema e que em todas as duas o numero maximo que consigo calcular e o fatorial de 20.
funcoes:
function Fatorial1(Numero: string): int64;
var
I, Aux: Integer;
begin
try
Aux := StrToInt(Numero);
Result := Aux;
for I := Aux downto 3 do
Result := Result * (I - 1);
if Result = 0 then
Result := 1;
except
Result := 0;
ShowMessage(´Impossivel de se Determinar o Fatorial do Numero´´ + Numero + ´´´);
end;
end;
function Fatorial2(Numero: integer): int64;
begin
if Numero = 0 then
result := 1
else
result := Numero * Fatorial2(Numero - 1);
end;
isso acontece porque o fatorial de 21 é igual a 51090942171709440000 e tamanho maximo suportado pelo tipo int664 e 2^63 = 9223372036854775808 isso quer dizer que o fatorial de 21 naum cabe no tipo int64.
como eu resolvo isso.
obrigado
tenho duas funcoes pra calculo de fatorial sendo uma delas com chamada recursiva a propria funcao. o problema e que em todas as duas o numero maximo que consigo calcular e o fatorial de 20.
funcoes:
function Fatorial1(Numero: string): int64;
var
I, Aux: Integer;
begin
try
Aux := StrToInt(Numero);
Result := Aux;
for I := Aux downto 3 do
Result := Result * (I - 1);
if Result = 0 then
Result := 1;
except
Result := 0;
ShowMessage(´Impossivel de se Determinar o Fatorial do Numero´´ + Numero + ´´´);
end;
end;
function Fatorial2(Numero: integer): int64;
begin
if Numero = 0 then
result := 1
else
result := Numero * Fatorial2(Numero - 1);
end;
isso acontece porque o fatorial de 21 é igual a 51090942171709440000 e tamanho maximo suportado pelo tipo int664 e 2^63 = 9223372036854775808 isso quer dizer que o fatorial de 21 naum cabe no tipo int64.
como eu resolvo isso.
obrigado
Tronbr
Curtidas 0
Respostas
Massuda
04/02/2005
Você realmente precisa lidar com números tão grandes assim? Nenhum dos tipos de dados nativos (tanto inteiros como ponto flutuante) são capazes de armazenar valores tão grandes sem perder precisão.
Para manipular número grandes você precisa implementar estruturas de dados/algoritmos para isso.
Uma abordagem simples é a mostrada [url=http://www.delphiforfun.org/Programs/big_factorials.htm]nesta página[/url] do site [url=http://www.delphiforfun.org/]www.DelphiForFun.org[/url].
Uma outra abordagem seria dar uma olhada nas bibliotecas para manipulação de inteiros grandes (´large integers´) disponíveis [url=http://www.freepascal.org/contrib/db.php3?category=Miscellaneous]nesta página[/url] para o FPC.
Para manipular número grandes você precisa implementar estruturas de dados/algoritmos para isso.
Uma abordagem simples é a mostrada [url=http://www.delphiforfun.org/Programs/big_factorials.htm]nesta página[/url] do site [url=http://www.delphiforfun.org/]www.DelphiForFun.org[/url].
Uma outra abordagem seria dar uma olhada nas bibliotecas para manipulação de inteiros grandes (´large integers´) disponíveis [url=http://www.freepascal.org/contrib/db.php3?category=Miscellaneous]nesta página[/url] para o FPC.
GOSTEI 0
Beppe
04/02/2005
Multiplicações de um inteiro de 32 se dá em uns poucos ciclos. Se isto tomar 1 unidade de tempo, uma multiplicação de um número de precisão arbitrária leva N**1.3 unidade de tempo, onde N é o número de words de memória.
qual seria a precisão dos números que precisa? Se for 128 bits, não é tão difícil de fazer in-line. Se não, precisará do algoritmo inteiro.
A idéia é a seguinte: Divida cada operando em duas partes, seja elas A e B, e C e D.
Resultado = AC**2n + (BC+AD)**n + BD
Multiplica UInt16 usando apenas operandos UInt8. Usa também shift e adição, mas estas são triviais de implementar.
qual seria a precisão dos números que precisa? Se for 128 bits, não é tão difícil de fazer in-line. Se não, precisará do algoritmo inteiro.
A idéia é a seguinte: Divida cada operando em duas partes, seja elas A e B, e C e D.
Resultado = AC**2n + (BC+AD)**n + BD
Multiplica UInt16 usando apenas operandos UInt8. Usa também shift e adição, mas estas são triviais de implementar.
procedure TForm1.Button1Click(Sender: TObject);
var
X, Y: Word;
Z: DWord;
begin
X := $0101;
Y := $0202;
// Z := X * Y;
Z := (HiByte(X) * HiByte(Y) shl 16) +
((LoByte(X) * HiByte(Y) + HiByte(X) * LoByte(Y)) shl 8) +
(Lo(X) * Lo(Y));
Caption := IntToHex(Z, 4);
end;GOSTEI 0
Beppe
04/02/2005
Ora, como sou desastrado...vc pediu fatorial, e eu lhe deu multiplicações. Bom, de fato, fatorial é uma série de multiplicações.
Mas eu já postei aqui uma implementação básica de BitInt´s:
http://forum.clubedelphi.net/viewtopic.php?t=39668&highlight=bigint+tbigint
A partir disso, pode fazer o que vc quer:
Eu poderia aumentar bastante a eficiÇencia destes códigos se eu tratasse alguns casos especiais, mas a performance de 800! é aceitável(mas não chequei se ultrapassa a precisão padrão, Dígitos=300)
B.
Mas eu já postei aqui uma implementação básica de BitInt´s:
http://forum.clubedelphi.net/viewtopic.php?t=39668&highlight=bigint+tbigint
A partir disso, pode fazer o que vc quer:
procedure TForm1.Button2Click(Sender: TObject);
var
Mult, Fac: BigNumber;
I: Integer;
begin
Memo1.Lines.Clear;
Mult := NewBigNumber(1);
Fac := NewBigNumber(1);
for I := 1 to 21 do
begin
Fac := Multiply(Fac, Mult);
Mult := Add(Mult, One);
Memo1.Lines.Add(IntToStr(I) + ´: ´ + BigNumberToStr(Fac));
end;
Edit2.Text := BigNumberToStr(Fac);
end;Eu poderia aumentar bastante a eficiÇencia destes códigos se eu tratasse alguns casos especiais, mas a performance de 800! é aceitável(mas não chequei se ultrapassa a precisão padrão, Dígitos=300)
B.
GOSTEI 0
Leitorbinario
04/02/2005
Preciso de uma função que calcule o fatorial de 100!. Alguem pode me ajudar?
GOSTEI 0
Motta
04/02/2005
Usando logaritmos
http://en.wikipedia.org/wiki/Stirling_series
http://en.wikipedia.org/wiki/Stirling_series
GOSTEI 0
Leitorbinario
04/02/2005
Alguem tem a função pronta?
GOSTEI 0
Motta
04/02/2005
http://www.efg2.com/Lab/Library/Delphi/MathFunctions/
parece ter, não se se funciona
parece ter, não se se funciona
GOSTEI 0
Leitorbinario
04/02/2005
Achei uma boa. valeu.
GOSTEI 0
Motta
04/02/2005
Publique a fonte, pode ser útil para alguem.
GOSTEI 0
Leitorbinario
04/02/2005
http://www.delphiforfun.org/Programs/big_factorials.htm
GOSTEI 0
Leitorbinario
04/02/2005
http://www.delphiforfun.org/Programs/big_factorials.htm
GOSTEI 0