! uitrekenen mbv log

[NetForce1]

Een halfjaar ofzo geleden kwam ik op nl.wetenschap een post tegen over een algoritme om ! uit te rekenen mbv logaritmen, dit in verband met de beperkte groote van primitieven (Het ging om de grootst mogelijke ! uit te rekenen op de computer).

Weet iemand hoe dit werkt, en kan het ook een beetje duidelijk uitleggen please? Heb nl nog niet echt superveel over logaritmen gehad (VWO-5)

[Tupolev]

Bedoel je misschien het berekenen hiervan m.b.v. van de gamma functie. Dat staat hier wel uitgelegd: http://astronomy.swin.edu.au/pbourke/analysis/gammafcn/

En hier staat een paar andere manieren die van de gammafunctie zijn afgeleid: http://numbers.computation.free.fr/Constants/Miscellaneous/gammaFunction.html

[Diadem]

pretty complex.

Kan iemand mij vertellen waarom er een t^x-1 staat, terwijl vervolgens x! = Gamma(x+1)

[Lord Daemon]

Het enige wat ik weet is dat Log (N!) = N log N - N, voor grote N. Maar het lijkt mij nauwelijks dat log een makkelijker algoritme is dan ! ?

[Tupolev]

Indien die x-1 er niet zou staan zou de gammafunctie er als volgt uit zien : int.e^-t*t^x dt. (int is het integraalteken)
Maar wanneer je dan dicht in de buurt van t=0 komt, wordt e^-t*t^x ongeveer t^x=1/t^-x.
En dit is een p-serie die convergeert als -x>1 oftewel x>-1. Dus het domein van de functie is (-1,+oneindig), en omdat we (0,+oneindig) als domein willen hebben (ooit wel eens gehoord van de faculteit van -1?), is er een translatie op de x-as nodig. Vandaar dat er x-1 staat i.p.v. x en x! = Gamma(x+1)

[NetForce1]

Het enige wat ik weet is dat Log (N!) = N log N - N, voor grote N. Maar het lijkt mij nauwelijks dat log een makkelijker algoritme is dan ! ?

niet makkelijker, alleen als je getallen te groot worden dan krijg je een fout bijv hier:

code:

int fac;

for (int i=1;i<=n;i++)
{
  fac *= i;
}

In JAVA is hier een BigInteger voor, ik weet alleen niet hoever die gaat.

[Confusion]

Lord Daemon, ik denk dat hij die bedoelt. Of eventueel de volledige Stirling benadering:

N! = (2*Pi*N)^(1/2)*N^N*exp(-N + 1/(12*N)+ O(N^(-2)))
en

log(N!) = 1/2log(2Pi) + (N+1/2)log(N) - N + 1/(12N) + O(N^(-2))

Aantonen dat dit juist is verloopt via de Gamma functie.

[Confusion]

ddewit schreef:
niet makkelijker, alleen als je getallen te groot worden dan krijg je een fout bijv hier:

Het is juist: hoe groter het getal, hoe kleiner de fout van de Stirling benadering.

[Diadem]

Op dinsdag 27 november 2001 00:25 schreef Tupolev het volgende:
Indien die x-1 er niet zou staan zou de gammafunctie er als volgt uit zien : int.e^-t*t^x dt. (int is het integraalteken)
Maar wanneer je dan dicht in de buurt van t=0 komt, wordt e^-t*t^x ongeveer t^x=1/t^-x.
En dit is een p-serie die convergeert als -x>1 oftewel x>-1. Dus het domein van de functie is (-1,+oneindig), en omdat we (0,+oneindig) als domein willen hebben (ooit wel eens gehoord van de faculteit van -1?), is er een translatie op de x-as nodig. Vandaar dat er x-1 staat i.p.v. x en x! = Gamma(x+1)

Ehm, dat maakt toch niets uit? Ik kan nu toch nog steeds -1! uitreken, dat is dan Gamma(0), en heeft gewoon een reele uitkomst, toch?

[NetForce1]

N! = (2*Pi*N)^(1/2)*N^N*exp(-N + 1/(12*N)+ O(N^(-2)))
en

log(N!) = 1/2log(2Pi) + (N+1/2)log(N) - N + 1/(12N) + O(N^(-2))

zal eens wat gaan proberen, alleen waar staat die O voor?

[NetForce1]

Het is juist: hoe groter het getal, hoe kleiner de fout van de Stirling benadering

Bij de code die ik gaf krijg je dus een fout, nl dat het getal niet in de int past.

[Confusion]

ddewit schreef:
zal eens wat gaan proberen, alleen waar staat die O voor?

Die staat voor het orde symbool van Landau. + O(1/N^2)betekent zoveel als: + alle termen (dat zijn er oneindig veel vaak) van orde 1/N^2 en lager (1/N^3, 1/N^4, ...)

In de benadering negeer je die, omdat de invloed ervan nihil is.

[cervelaatworst]

Op dinsdag 27 november 2001 14:37 schreef Diadem het volgende:

[..]

Ehm, dat maakt toch niets uit? Ik kan nu toch nog steeds -1! uitreken, dat is dan Gamma(0), en heeft gewoon een reele uitkomst, toch?

Ik denk omdat je wil dat Gamma (1) = 1

[Tupolev]

Op dinsdag 27 november 2001 17:24 schreef cervelaatworst het volgende:

[..]

Ik denk omdat je wil dat Gamma (1) = 1

ja dat klopt.