Fibonacci parallelisieren

Wie kann man Fibonacci Reihen Berechnung parallelisieren?

volkard

qdk schrieb:

Wie kann man Fibonacci Reihen Berechnung parallelisieren?

Einfach in den unteren Ebenen spalten, also die beiden Funktionsaufrufe so gestalten, daß sie in eigenen Threads laufen.
Aber die naive Implementierung ist soo schlecht, daß Parallelisierung auch nicht viel bringt.
Ob man sowas http://www.chaos.org.uk/~eddy/craft/Fibonacci.html parallelisieren will, ist dann wieder eine andere Frage.

volkard schrieb:

qdk schrieb:

Wie kann man Fibonacci Reihen Berechnung parallelisieren?

Einfach in den unteren Ebenen spalten, also die beiden Funktionsaufrufe so gestalten, daß sie in eigenen Threads laufen.

Aber das bringt doch nix, außer das zwei Threads das gleiche berechnen.

DerBaer

ich würde sagen, dass man die Reihe nicht parallelisieren kann(zumindest nicht dass es schneller wird), da die n-te Zahl abhängig von der n-1-ten Zahl ist und diese somit als erstes berechnet werden muss.
Wenns schnell gehen muss (bei großen Zahlen) empfiehlt sich dann die absolute Berechnungsformel.

knivil

qdk schrieb:

Wie kann man Fibonacci Reihen Berechnung parallelisieren?

Unnoetig, da die besseren Algorithmen schon wahnsinnig schnell sind.

Jester

DerBaer schrieb:

ich würde sagen, dass man die Reihe nicht parallelisieren kann(zumindest nicht dass es schneller wird), da die n-te Zahl abhängig von der n-1-ten Zahl ist und diese somit als erstes berechnet werden muss.
Wenns schnell gehen muss (bei großen Zahlen) empfiehlt sich dann die absolute Berechnungsformel.

Da irrst Du Dich aber. Sogar sequenziell kann man die n-te Zahl in O(log n) Zeit berechnen. Wie das geht steht auch in dem Link, den schon jemand gepostet hat.

Ich vermute auch, dass man durch Parallelisierung nichts mehr gewinnen kann. Beim Parallelisieren bleiben oft so logarithmische Laufzeiten übrig, die von der Kommunikation herkommen. Wenn man schon mit sowas anfängt, glaube ich kaum, dass man es weg bekommt. Aber das ist natürlich nur eine Intuition.

Jester schrieb:

Ich vermute auch, ... Aber das ist natürlich nur eine Intuition.

http://www2.roguewave.com/developer/Parallel_Computing_Strategies.pdf
(Seite 13)

zum Link vom volkard:

zum Thema Intuition: ließe sich sowas(Fibonaccis/sekunde) nicht auch leicht ausrechnen (inclusive Speicherzugriffszeiten etc)(was schafft so ein 1055 wenn man von 64bit ausgeht und mal annimmt, die Integerzahlen werden nicht größer als 64bitmax und die Zwischenergebnisse werden in allen möglichen Registern/Prozessoren zwischengelagert)?

Jester

zli schrieb:

Jester schrieb:

Ich vermute auch, ... Aber das ist natürlich nur eine Intuition.

http://www2.roguewave.com/developer/Parallel_Computing_Strategies.pdf
(Seite 13)

[/quote]

Natürlich kann man denkbar blödesten Algorithmus nehmen und den durch Parallelisierung schneller machen. Ich sprach aber vom besten (bekannten), und da sehe ich's nach wie vor nicht.

Der in den Slides verwendete Algorithmus hat exponentielle Laufzeit. Selbst wenn man den nun auf nem riesigen Cluster laufen lässt bleibt die Laufzeit exponentiell.

Der Algorithmus, aus volkards Link mit dem Square-And-Multiply einer 2x2-Matrix hat aber nur logarithmische Laufzeit um die n-te Zahl auszurechnen. Diesen 8-fachen Durchsatz aus den Slides können sie sich eigentlich grad in die Haare schmieren, wenn mans auf dem einen Core geschickt macht, ist man deutlich schneller. Aber das schreibt man natürlich nicht auf seine Slides. Selbst dann nicht, wenn man es weiß.

krümelkacker

Jester schrieb:

Der Algorithmus, aus volkards Link mit dem Square-And-Multiply einer 2x2-Matrix hat aber nur logarithmische Laufzeit um die n-te Zahl auszurechnen.

Ui. Das klingt interessant. Lass mich mal überlegen, wie das gehen soll. ...

n
|0 1|  . |0| = |fib_{n+0}|
|1 1|    |1|   |fib_{n+1}|

Aber wieso noch Square-And-Multiply? Wozu gibt es denn Eigenwertzerlegungen? Man kann die Matrix-Potenz auch direkt ausrechnen. Sei g der goldene Schnitt (1,618...). Dann gilt in diesem Fall

n                                 n
|0 1|   =  1/(g^2+1)  | g 1| * |-1/g 0|  * | g -1|
|1 1|                 |-1 g|   |  0  g|    | 1  g|

Und da die mittlere Matrix eine Diagonalmatrix ist, ist das Pozenzieren um so einfacher:

n
|0 1|   =  1/(g^2+1)  | g 1| * |(-1/g)^n  0 |  * | g -1|
|1 1|                 |-1 g|   |   0     g^n|    | 1  g|

Und siehe da, das sieht fast genauso aus wie das, was man auf Wikipedia finden kann. Die direkte Formel ist dann

long fib(int n)
{
   const double sqrt5 = std::sqrt(5.0);
   const double p1 = std::pow((1.0+sqrt5)/2.0,n);
   const double p2 = std::pow((1.0-sqrt5)/2.0,n);
   return static_cast<long>(1.0/sqrt5 * (p1-p2) + 0.5);
}

Jester

Ja klar, mit Gleitkommazahlen kann man noch ein bißchen was schummeln.
Wäre mal interessant zu sehen, wie lange das gut funktioniert und ab wann die Rundungsfehler das erste Mal die Ergebnisse verfälschen.

edit: habs probiert, bei 76 geht schief.

Error: fib(76) is 3416454622906706, should be 3416454622906707
Ab 94 sind die Rundungsfehler dann so groß, dass konsequent 0 rauskommt.

Natürlich kann man die Eigenwertzerlegung trotzdem benutzen, wenn man auf Fließkommazahlen verzichten will, muß dann aber mit algebraischen Zahlen rechnen...

krümelkacker

Jester schrieb:

Ab 94 sind die Rundungsfehler dann so groß, dass konsequent 0 rauskommt.

Das sind strengenommen keine Rundungsfehler mehr sondern ein möglicher Effekt von undefiniertem Verhalten.