Fakultät in logarithmischer Lauftzeit berechnen

volkard

http://www.luschny.de/math/factorial/SrcJava/FactorialSimpleSwing.html

CBR-Racer

also sehe meinen Prof wirklich nur sehr selten am We ... aber werde es, wenn dann auch erst nächste Woche Freitag erfahren ... bis dahin habe ich Zeit ... und es wäre absolut genial, wenn ich das irgendwie hinkriegen würde ...

TGGC

volkard schrieb:

http://www.luschny.de/math/factorial/SrcJava/FactorialSimpleSwing.html

Wie kann das logarithmische Laufzeit haben? Das for in swing() läuft doch mit O(n), weil die Schleife n Schritte macht. Zwar nicht auf einmal, aber insgesamt schon, da m ja nur im Schleifenkopf geändert wird.

volkard

TGGC schrieb:

volkard schrieb:

http://www.luschny.de/math/factorial/SrcJava/FactorialSimpleSwing.html

Wie kann das logarithmische Laufzeit haben? Das for in swing() läuft doch mit O(n), weil die Schleife n Schritte macht. Zwar nicht auf einmal, aber insgesamt schon, da m ja nur im Schleifenkopf geändert wird.

korrekt. hat lineare. dabei sah das so schnell aus.
ich überleg morgen den ganzen tag, aber ich fürchte, da find ich nix.

@CBR-Racer: was habt ihr gerade an vorlesungsstoff dran? vielleicht gibt das uns nen tip.

WebFritzi

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.

SG1

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

Bin jetzt zu muede, die genaue Definition nachzuschlagen, aber auf jedenfall ist O(n/2) = O(n). Und damit sind wir wieder am Anfang.

WebFritzi

SG1 schrieb:

Bin jetzt zu muede, die genaue Definition nachzuschlagen, aber auf jedenfall ist O(n/2) = O(n). Und damit sind wir wieder am Anfang.

Na jut, dann ist das wohl diese lineare Geschichte.
$O(n) = \{f: \mathbf{N}\to\mathbf{R}\,|\, \exists a,b\in\mathbf{R}\;mit\; f(n) = an + b\}$

Gregor

Ich weiß garnicht, warum hier jeder irgendwas kompliziertes berechnen will. Es ist vollkommen legitim und natürlich, bei einer Funktion, die nur für etwa 20 Werte sinnvolle Ergebnisse liefert, die Ergebnisse einfach direkt in den Quellcode zu schreiben. Schreib sie in ein Array, dann kriegst du O(1), wenn dir das zu schnell ist und du nichts schnelleres als O(log(n)) haben möchtest (wobei O(1) eigentlich in O(log(n)) liegt), dann schreib sie halt in nen Baum und such sie dir mit binärer Suche raus.

Oder sollt ihr die Funktion für einen Datentyp schreiben, der ein paar hundert Stellen lange Zahlen erlaubt?

Gregor

WebFritzi schrieb:

SG1 schrieb:

Bin jetzt zu muede, die genaue Definition nachzuschlagen, aber auf jedenfall ist O(n/2) = O(n). Und damit sind wir wieder am Anfang.

Na jut, dann ist das wohl diese lineare Geschichte.
$O(n) = \{f: \mathbf{N}\to\mathbf{R}\,|\, \exists a,b\in\mathbf{R}\;mit\; f(n) = an + b\}$

Deine Definition ist falsch. Die O-Notation ist wie folgt definiert:

O(g(n)) = {f:N->R | Es gibt ein c aus R+ und es gibt ein n0 aus N, so dass für alle n >= n0 gilt: |f(n)| <= c|g(n)|}

WebFritzi

Na gut. Ist ja so ähnlich. Also
$O(n) = \{f: \mathbf{N}\to\mathbf{R}\,|\, \exists a,b\in\mathbf{R}^+\;mit\; |f(n)| \le an + b\}$

CBR-Racer

also vom Thema kommt man leider auch nicht auf die Lösung, weil Thema ist ganz einfach Einführung in C ... und da ich da schon mal nen Vorlesung drüber hatte, kriege ich jetzt regelmäßig schwierigere Aufgaben ... die anderen müssen das ganze nur rekursiv programmieren ... echt schwer ... naja was solls ...

@ Gregor ... nein nichts mit Datentyp oder so, aber ich denke, das ist auch nicht der Trick, den der prof meinte ... wenn es überhaupt einen Trick gibt ...vielleicht soll ich ja auch einfach nur drauf kommen, daß es so einen Algorithmus gar nicht gibt ...

@ WebFritzi ... das ist leider auch wieder linear, aber sah echt interessant aus die Rechnung ... muss ich mri auf jedenfall merken ...

Ich würde für alle n<=10 die Werte in eine Tabelle schreiben. Für n>10 kann man die Stirling-formel benutzen, aus der sich ergibt:

ln(n!) ~ (n+1/2) * ln n - n + ln(2*PI)

Für n>10 liefert das sehr genaue Werte und sollte in logarithmischer Zeit laufen ... denk ich ...

Gruß

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

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