Fakultät in logarithmischer Lauftzeit berechnen

[Jester]

Nein, das läuft in konstanter Zeit... außerdem ist es nicht 100% exakt.

@Gregor: Es geht hier darum einen Algorithmus für Fakultät zu implementieren und zwar für einen beliebigen Datentyp. Deine Antwort ist aus Sicht eines Implementierers zwar vernünftig, aber aus der Sicht der Informatik paßt sie nicht zur Aufgabenstellung. Auch Sortierung läßt sich in O(1) erledigen. Einfach alle möglichen Ordnungen als Index in die Tabelle der korrekt sortierten Mengen verwenden. Jede Funktion ist über einem endlichen Definitionsbereich O(1), aber das ist hier nicht der Punkt.

Zum Thema n! fällt mir leider auch nicht viel ein, das heißt eines eben doch:

wir können zum Beispiel

(2*n)! = Produkt(alle ungeraden Zahlen < n) * 2^n * (n/2)! die rechte Seite krieg man also klein(2^n ist sehr gut berechenbar). Das Problem sind die ungeraden Zahlen, kann man da auch was machen? Oder bringt es was die Produkte der ungeraden Zahlen links+rechts irgendwie durch quadrieren wiederzuverwenden?

MfG Jester

[Kloputzer]

Im Übrigen:
Will man n! nach den bisherigen Ansätzen für beliebig große Zahlen implementieren, dann sind diese sogar noch wesentlich schlechter als O(n), da auch die Multiplikation mit größerem n WESENTLICH aufwendiger wird. Was auch der Grund ist, weswegen ein Rechner eine gute lange lange Zeit beschäftigt ist um 1.000.000! auszurechnen.

Ich weiß, dass die Stirling - Formel verbesserbar ist. Allerdings weiß ich
nicht ob diese Verbesserung beliebig weitergeführt werden kann.

[Jester]

Jo klar, da es hier aber um die theoretische Komplexität der Berechnung von n! geht tun wir einfach mal so, als sei das multiplizieren dieser riesigen Zahlen kein Problem. Wir wollen nur schaun, ob wir das hinkriegen.
Die Multiplikation sehr großer Zahlen ist ein Problem für sich, bis jetzt kommt man da auf O(n*log n) (FFT). Ob das auch untere Schranke ist weiß ich leider nicht.

MfG Jester

[CBR-Racer]

also bin euch echt dankbar für die vielen Antworten und Ideen ... werde mir halt ne Liste mit Ideen machen und die dem Prof präsentieren (wenn ich nicht drauf kommen sollte) ... damit er sieht, ich habe mich damit beschäftigt ...
aber ist echt ne knifflige Sache

[TGGC]

Wegen den grossen Multiplikationen gäbe es ja evtl. den Ansatz erstmal nur die Logarithmen zu addieren?

[Jester]

Die Frage ist dann wiederum wie berechne ich den Logarithmus schnell. Und dafür brauche ich vor allem Zahlen die Nachkommastellen können und das ist irgendwie ärgerlich, wenn ich sonst nur einfache Integers habe, weil dann wieder die Rechengenauigkeit eine Frage wird.

MfG Jester

[xroads42]

(dumme) Idee:
gegeben sei ein array A mit allen primazahlen <=n.

Psydocode:

for a=1 to |A| do
	for i=A[a] to n step A[a] do // *
 		B[A[a]]+=berechne wie oft i durch a teilbar; //*
	od
od
n=1
for b=1 to |B| do
	n=(A[b]^B[b])*n;
od

*= vielleicht gibt es hier eine geschlossene Formel??

ich denke, wenn das überhaupt funzt, ist das Problem A zu erstellen...Aber selbst dann wäre das nicht O(logn)....

Nicht haua machen wenn flasch sein

[xroads42]

WebFritzi schrieb:

Ich weiß nun nicht genau, wie die Laufzeit berechnet wird. Ich denke mal, dass es die Anzahl der Multiplikationen in Abh. von n sind. Dann habe ich auf jeden Fall einen Algo gefunden, der die Fakultät in O(n/2) ausrechnet (wenn man das Multiplizieren mit 2 nicht mitrechnet ). Es ist ja z.B.

8! = 5 * ((5-1)(5+1)) * ((5-2)(5+2)) * ((5-3)(5+3))
   = 5 * (25-1²) * (25-2²) * (25-3²)

Mit q = (n/2 + 1) gilt allgemein

n! = q * (q²-1²) * (q²-2²) * ... * (q²-(q-2)²)

Setzen wir nun
$a_k = q^2 - k^2,$
dann gilt
$a_{k+1} = (q^2 - k^2) - 2k - 1 = a_k - (2k + 1).$
Wenn wir nun die Multiplikation mit 2 vernachlässigen, so können wir also a_k+1 aus a_k ohne Aufwand berechnen. Da nun
n! = q \cdot a\_1 \cdot a\_2 \cdot \dots \cdot a_{q-2},
haben wir
$q-2 = \frac{n}{2} + 1 - 2 = \frac{n}{2} - 1$
Multiplikationen.

EDIT: Bei ungeradem n kommt noch eine Multiplikation mit n dazu.

Könnte man a! in 2 Polynome mit grad n aufspalten so könnte man diese mit der FFT (Fast Fourier TRafo.) ind O(nlogn) multipizieren.....

[volkard]

xroads42 schrieb:

ich denke, wenn das überhaupt funzt, ist das Problem A zu erstellen...Aber selbst dann wäre das nicht O(logn)....

jo. zwischen 1 und n gibt es circa n/ln(n) primzahlen.
alle primzahlmultiplizierer brauchen also mindestens O(n/ln(n)) und das ist leider viel großer als O(ln(n)).

[TGGC]

Na ich bin jedenfalls gespannt, wie der Prof aus der Sache wieder rauskommt.

Bye, TGGC

[CBR-Racer]

also ich bin auch mal gespannt ... weil denke nicht, daß ich bis Freitag eine Lösung habe ... muss auch noch bis Donnerstag nen Vortrag zum Thema VPN für eine andere Vorlesung vorbereiten und habe einfach genug zu tun ...

habe mich aber trotzdem nochmal ein wenig beschäftigt mit der ganzen Sache und habe mal drüber nachgedacht ... es gab mal einen Algorithmus mit dem ich 2 natürliche Zahlen in logarithmischer Laufzeit berechnen kann ... aber das brachte mich dann wieder auch nicht weiter ... wollte die Zahlen dann variabel lassen und die Zahlen für die Fakultät einsetzen aber dadurch hat das ganze ja wieder keine logarithmische Laufzeit

[LIBS]

Wollte den Thread mal wieder nach vorn holen ... heute ist doch die Antwort fällig, ne?

Gruß

[Jester]

Hab heut morgen auch schon dran gedacht.

[SG1]

*gespanntsei*

[CBR-Racer]

*Trommelwirbel*

Und hier präsentier ich euch die Lösung ...

also ihr werdet es kaum glauben ... also der Prof sprach mich heute an und fragte, ob ich die Aufgabe geschafft hätte ... ich sagte mit herabgesenktem Kopf nein ... fragte aber auch gleich wie man die Fakultät in logarithmischer Laufzeit berechne ... er schaute nur etwas verdutzt und fragte, ob er wirklich Fakultät gesagt hätte ... das wurde ihm dann von mehreren Leuten bestätigt ... er entschuldigte sich höflich ... was er eigentlich wollte war ein Algorithmus um die Fibonacci-Zahlen in logarithmischer Lauftzeit ...

*lach* naja sorry Leute ... aber war nicht meine Schuld ... jetzt muss ich mir mal Gedanken über die neue "richtige" Aufgabe machen

[Gregor]

Ich weiß die Lösung! ...ich weiß sogar 2 Lösungen!

[CBR-Racer]

du meinst jetzt für die Fibonacci-Zahlen in logarithmischer Laufzeit ?? .... her damit

[Gregor]

Du sollst ja auch noch etwas zu tun haben, aber ich gebe dir nen Tipp:

Es gibt für die Fibonaccizahlen eine explizite Formel (die also nicht rekursiv ist). Ich denke, dass man diese Formel leicht so implementieren kann, dass sie in logarithmischer Zeit berechnet werden kann.

...jetzt mußt du nur noch die Formel herausfinden!

...die zweite Lösung war natürlich:

Alles vorher ausrechnen und in nem Array speichern. Bei den 46 (glaube ich, mich zu erinnern) Fibonaccizahlen, die man auf herkömmlichen Wegen darstellen kann, ist das IMHO immer noch eine vollkommen legitime, richtige und natürliche Lösung. Es ist sogar die beste Lösung.

[CBR-Racer]

THX ... muss dazu sagen, die Formel für die Fibonacci-Zahlen habe ich schon ... jetzt muss ich nur nochmal nen Prog dazu schreiben und das in logarithmischer Zeit ... aber das mach ich erst morgen oder so ... muss mich noch ein wenig um meine HP´s kümmern und Tagesguck schauen ...

war nur auf die zweite Lösung gespannt ...

[xroads42]

Ich machs in O(1) *gg*