WICHTIG: Der Betrieb von goMatlab.de wird privat finanziert fortgesetzt. - Mehr Infos...

Mein MATLAB Forum - goMatlab.de

Mein MATLAB Forum

  
Gast > Registrieren       Autologin?   

Partner:




Forum
      Option
[Erweitert]
  • Diese Seite per Mail weiterempfehlen
     


Gehe zu:  
Neues Thema eröffnen Neue Antwort erstellen

Fibonacci-Zahlen möglichst effizient
 

Apoo

Gast

Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 04.06.2019, 19:06     Titel: Fibonacci-Zahlen möglichst effizient
  Antworten mit Zitat      
Hallo zusammen,

ich hätte hier eine Frage bzw. Aufgabenstellung, zu der ich gerne eure Meinung wissen würde:
Ich soll eine Matlab-Funktion definieren, die zu ihrem Argument die entsprechende Fibonacci-Zahl berechnet. Dabei ist darauf zu achten, dass der Programmtext möglichst kurz ist (also möglichst wenig Zeilen) und die Laufzeit für ein (großes) Argument möglichst kurz ist.
Meine erste Idee war, die Fibonacci-Zahlen rekursiv zu berechnen:
Code:
function f = fib(n)
if(n==1 | n == 2)
  f = 1;
else
  f = fib(n-1) + fib(n-2);
end

Was die Kürze des Programmtextes angeht, ist das wohl kaum zu übertreffen. Allerdings meine ich gehört zu haben, dass rekursive Programme im Allgemeinen (bzw hier für große Argumente) langsamer sind als die iterativen Varianten.
Deshalb war meine zweite Idee folgende:
Code:
function erg = fibo(k)
f1=1;
f2=1;
if (k == 1 | k == 2)
  erg = 1;
else
  for i = 3:k
    f3 = f2 + f1;
    f1 = f2;
    f2 = f3;
  end
  erg = f3;
end

Jetzt würde mich interessieren, welche Variante ihr unter den oben genannten Bedingungen empfehlen würdet?
Vielen Dank für eure Hilfe! Smile
PS: Ich hoffe dass die Programme soweit stimmen, ich bin noch nicht dazu gekommen, sie auszutesten.


Harald
Forum-Meister

Forum-Meister

Beiträge: 24.448
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2017b
     Beitrag Verfasst am: 04.06.2019, 20:21     Titel:
  Antworten mit Zitat      
Hallo,

effizienter dürfte das sein:
https://de.wikipedia.org/wiki/Golde....._mit_den_Fibonacci-Zahlen

Grüße,
Harald
_________________

1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)
Private Nachricht senden Benutzer-Profile anzeigen
 
Jan S
Moderator

Moderator

Beiträge: 11.057
Anmeldedatum: 08.07.10
Wohnort: Heidelberg
Version: 2009a, 2016b
     Beitrag Verfasst am: 07.06.2019, 17:14     Titel: Re: Fibonacci-Zahlen möglichst effizient
  Antworten mit Zitat      
Hallo Apoo,

Wie Harald schon erwähnte - Formel von Binet:
Code:
function x = fibo1(n)
f = sqrt(5);
x = ((1 + f)^n - (1 - f)^n) / (f * 2^n);

Das ist von der Laufzeit für große n natürlich deutlich besser als Rekursionen oder Iterationen. Mit pow2(n) wäre es noch ein bisschen effizienter als mit dem allgemeinen 2^n .

Vielleicht ist die Umformung auch schneller:
Code:
function x = fibo2(n)
f = 0.5 + 0.5 * sqrt(5);
x = (f^n - (1 - f)^n) / sqrt(5);


Oder noch besser mit Konstanten:
Code:
function x = fibo3(n)
x = round((1.618033988749895^n - (-0.618033988749895)^n) / 2.23606797749979);


Im rekursiven Code kannst Du:
Code:
if(n==1 | n == 2)

vereinfachen zu:
Code:


Oder noch kompakter:
Code:
function f = fibo4(n)
f = 1;
if n > 2
  f = fibo4(n-1) + fibo4(n-2);
end


Deinen nicht-rekursiven Code kann man auch noch zusammenfassen:
Code:
function erg = fibo5(n)
f1 = 1;
f2 = 1;
erg = 1;
for i = 3:n
    erg = f1 + f2;
    f1 = f2;
    f2 = erg;
end

Das ist zwar schön einfach, aber grottig langsam.

Code:
tic
for k = 1:100
    for n = 1:200
        x = fibo3(n);
    end
end
toc

Das benötigt auf Matlab-Online 0.18 sec, mit fibo5 14 sec und das rekursive fibo4 rattert seit Minuten vor sich hin. Ich nehme an, eine lokale Matlab Installation ist da schneller.

Zum Vergleich wäre noch eine Look-up-Tabelle sinnvoll. Inputs oberhalb von 1475 ergeben Inf, es reicht also die ersten 1474 Werte zu berechnen:
Code:
function f = fibo4(n)
persistent P
if isempty(P)
    v = 1:1474;
    P = round((1.618033988749895.^v - (-0.618033988749895).^v) ./ 2.23606797749979);
end
f = P(n);
end

Das ist in Matlab Online langsamer als fibo3, aber das solltest Du auch noch mal messen.

Nun habe ich deine Aufgabe noch nicht ganz gelöst - zum Glück. Es bleibt noch zu entscheiden, ob Code-Länge, Laufzeit oder Code-Komplexität wichtiger sind.

Gruß, Jan
Private Nachricht senden Benutzer-Profile anzeigen
 
Neues Thema eröffnen Neue Antwort erstellen



Einstellungen und Berechtigungen
Beiträge der letzten Zeit anzeigen:

 Du kannst Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.
Du kannst Dateien in diesem Forum posten
Du kannst Dateien in diesem Forum herunterladen
.





 Impressum  | Nutzungsbedingungen  | Datenschutz | FAQ | goMatlab RSS Button RSS

Hosted by:


Copyright © 2007 - 2024 goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks

MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.