Allgorithmus für Fakultät in logarithmischer Laufzeit

[CBR-Racer]

Hallo Leute
ich habe es schon in etlichen Foren probiert, ich versuch es auch noch einfach mal hier ... vielleicht habe ich ja Glück ...

also wie das Thema schon sagt, brauch ich einen Algorithmus für die Fakutät in logarithmischer Laufzeit ...

kann mir jemand helfen ??

danke schon mal ...

[Christian Kruse]

Hallo CBR-Racer,

ich habe es schon in etlichen Foren probiert,
ich versuch es auch noch einfach mal hier ...
vielleicht habe ich ja Glück ...

Wohl kaum.

also wie das Thema schon sagt, brauch ich einen
Algorithmus für die Fakutät in logarithmischer
Laufzeit ...

Den gibt es nicht. Die Laufzeit fuer einen
Fakultaets-Algorithmus ist bestenfalls linear, mit
etwas pech sogar quadratisch -- je nach dem, wie
du die Verwaltung grosser Zahlen machst. Du kommst
halt nicht drum herum, alle Elemente von 2 bis n
einschliesslich miteinander zu multiplizieren.

Gruesse,
 CK

[Sven Rautenberg]

Moin!

also wie das Thema schon sagt, brauch ich einen
Algorithmus für die Fakutät in logarithmischer
Laufzeit ...

Den gibt es nicht. Die Laufzeit fuer einen
Fakultaets-Algorithmus ist bestenfalls linear, mit
etwas pech sogar quadratisch -- je nach dem, wie
du die Verwaltung grosser Zahlen machst. Du kommst
halt nicht drum herum, alle Elemente von 2 bis n
einschliesslich miteinander zu multiplizieren.

Mag ja sein, dass es bei der Gamma-Funktion eine allgemeine Darstellung bzw. Sonderfallbehandlung für natürliche Zahlen gibt, die sich auch logarithmisch ansteigend berechnen läßt.

http://www.mathe.braunling.de/Gammafkt.htm zeigt jedenfalls jede Menge komplexe Formeln, die auseinanderzunehmen ich mich um diese Zeit nicht mehr in der Lage fühle.

Ich denke nur, dass sich Produkte oder Integrale von Null bis Unendlich oder Limes gegen Unendlich nicht so wirklich in logarithmischer Zeit berechnen lassen.

- Sven Rautenberg

[Harry]

Holladiewaldfee,

Den gibt es nicht. Die Laufzeit fuer einen
Fakultaets-Algorithmus ist bestenfalls linear, mit
etwas pech sogar quadratisch -- je nach dem, wie
du die Verwaltung grosser Zahlen machst. Du kommst
halt nicht drum herum, alle Elemente von 2 bis n
einschliesslich miteinander zu multiplizieren.

Hm, nö.
Die Fakultät ist definiert (!) durch das Integral über die Gammafunktion (Euler-Intergral zweiter Gattung):

x! := Gamma(x+1)

wobei (Maple-Syntax)

Gamma(x) := int(exp(-t) * t^(x-1), t=0..infinity)

also:

x! = int(exp(-t) * t^x, t=0..infinity)

Tja, dieses Integral gehört aber auch zu den Dingen, die wenig Spaß machen. Wenn er es schafft, das halbwegs vernünftig zu lösen könnte er am Ende schneller sein, als wenn er alle Zahlen miteinander multipliziert ;)

Dann gibt's da noch 'ne Näherung, die glaube ich aus der Stirling'schen Formel folgt:

ln(x!) ~ (x + 0.5) * ln(x) - x + ln(sqrt(2*Pi))

Lässt sich umformen zu

x! = exp(-x) * x^x * sqrt(2*Pi*x)

Zumindest das sollte dann schneller gehen als die ganzen Zahlen rauf und runter zu multiplizieren ... vielleicht ;)

Bloß ob der natürlich logarithmisch ist sei mal dahingestellt. Dafür kenn ich mich zu wenig mit so'm Zeug aus ;)

Ciao,

Harry

[Frank Schönmann]

hi!

x! = exp(-x) * x^x * sqrt(2*Pi*x)

Davon habe ich auch schon verschiedene Varianten gesehen, die sich
zwar alle ähneln, aber nicht hundertprozentig identisch sind.
Allerdings ist Stirlings Approximation wirklich die schnellste
Methode zu Berechnung der Fakultät. Darüber, wie effizient das nun
ist, will ich aber auch nicht nachdenken... ;)

bye, Frank!

[Hans35]

Never argue with an idiot. He will lower you to his level and then

beat you with experience.

[MudGuard]

Hi,

Allerdings ist Stirlings Approximation wirklich die schnellste
Methode zu Berechnung der Fakultät.

Nein, es ist eben keine Methode zur Berechnung, sondern zur Annäherung - darum auch Approximation.

2! = 1 * 2 = 2
exp(-2) * 2^2 * sqrt(2*Pi*2) =~ 1,9190043514889831578885840261887

1,9190043514889831578885840261887 != 2

Ok, ließe sich durch Runden noch korrigieren.

3! = 1 * 2 * 3 = 6

exp(-3) * 3^3 * sqrt(2*Pi*3) =~ 5,8362095913458639956126939375812

5,8362095913458639956126939375812 != 6

Der Unterschied ist größer geworden, ließe sich aber durch Runden noch korrigieren.

10! = 3628800
exp(-10) * 10^10 * sqrt(2*Pi*10) = 3598695,6187410359216231759328292

Der Unterschied ist hier immerhin schon 30104,381258964078376824067170758 - also nicht mehr durch Runden wegzubekommen.

cu,
Andreas

[Harry]

Holladiewaldfee,

Allerdings ist Stirlings Approximation wirklich die schnellste
Methode zu Berechnung der Fakultät.

Nein, es ist eben keine Methode zur Berechnung, sondern zur Annäherung - darum auch Approximation.

Die Form

ln(x!) ~ (x + 0.5) * ln(x) - x + ln(sqrt(2*Pi))

gehört wirklich nicht zu den schlechtesten Approximationen der Fakultät.

Die eigentliche Stirling-Formel ist da noch viel schlechter.
Ableitung:

ln(x!) = ln(1*2*...*x) = ln(1)+ln(2)+...+ln(x) = sum(y=1..x, ln(y))

Für große x kann man das durch ein Integral darstellen:

ln(x!) = int(y=1..x, ln(y)) = x*ln(x)-x+1

Wenn x jetzt wirklich groß ist läßt ma das "1-x" unter'n Tisch fallen und schreibt nur noch:

ln(x!) = x*ln(x)

Hier hat man wirklich einiges vernachlässigt, vor allem der Rausfall des -x+1 schlägt sich durch.

Wie man von hieraus (oder überhaupt) aber auf die zuerst genannte Formel kommt ist mir vollkommen schleierhaft, das kann ich (noch) nicht herleiten :(

Ich hab aber grade mal meine Formelsammlung gewälzt und noch eine andere Formel gefunden, die genauer sein müsste als die ganz oben, da die obige als Näherung aus der unteren hervorgeht:

n! = (n/e)^n*sqrt(2*Pi*n)*(1 + 1/(12*n) + 1/(288*n^2) + ...)

Die erste Formel erhält man, wenn man beim ersten Glied (=1) abbricht.

Ciao,

Harry