Getallen van Fibonacci berekenen.

[Cycloon]

Omdat in vele talen, een int standaard de waarde 0 krijgt.

Laat het nu net zo zijn dat dit in c/c++ niet gebeurt. De initialisatie gebeurt zoals rogier zei in de volgende functie aanroep.

[Lathander]

Waarom roept die methode zichzelf op?

Dat is om problemen vragen.

[Rogier]

Waarom roept die methode zichzelf op?

Dat is om problemen vragen.

Wablief? Nou is het voorbeeld van TS nogal een lelijke functie, maar als je vindt dat recursie om problemen vraagt, zou ik graag een 'minder problematische' oplossing zien dan:

Code: Selecteer alles

int Fibonacci( int n )

{

  if (n<3) return 1;

  return Fibonacci(n-1) + Fibonacci(n-2);

}

(okee vooruit, behalve

Verborgen inhoud

Code: Selecteer alles

#include <math.h>

int Fibonacci( int n )

{

  static const double s5 = sqrt(5);

  return int((pow(1+s5,n)-pow(1-s5,n))/(pow(2,n)*s5));

}

dan)

[Cycloon]

Recursie wordt inderdaad regelmatig gebruikt omdat het problemen opsplitst in kleinere deeltjes en het oplossen zo makkelijker maakt. Bv de snelste sorteeralgoritmes voor tabellen gebruiken recursie. Recursieve formules komen ook dikwijls voor in de wiskunde en zo kunnen we nog wel even doorgaan.

Je kan recursie altijd zelf gaan simuleren met code maar dat zal nauwelijks effectiever zijn dan te doen aan de hand van functies die zichzelf oproepen.

[Rogier]

Bv de snelste sorteeralgoritmes voor tabellen gebruiken recursie.

(off-topic opmerking:

Verborgen inhoud

de snelste sorteeralgo's zijn volgens mij lineair

)

Je kan recursie altijd zelf gaan simuleren met code maar dat zal nauwelijks effectiever zijn dan te doen aan de hand van functies die zichzelf oproepen.

Precies, en tenzij de recursie-relatie heel simpel is (zoals in het geval van faculteiten bijvoorbeeld, daar is een for-loop wel wat efficienter dan een recursieve functie) maak je de boel alleen maar warrig door het helemaal uit te programmeren. Terwijl in de praktijk nog steeds hetzelfde rekenwerk gedaan wordt.

[Cycloon]

(off-topic opmerking:

Verborgen inhoud

de snelste sorteeralgo's zijn volgens mij lineair

)

Ik meende mij te herinneren dat het snelste sorteer algoritme dmv recursie de tabel telkens halveert en zo de tabel gaat sorteren. Ik kan me niet meer herinneren hoe het precies ging (het was iets meer dan dat) dus het kan zijn dat er misschien toch nog betere zijn

[Lathander]

Persoonlijk vind ik dat je best lussen gebruikt om zoiets te doorwerken. Dan kan je er op de koop toe nog eens bij instellen hoe ver je wil gaan.

[Cycloon]

Persoonlijk vind ik dat je best lussen gebruikt om zoiets te doorwerken. Dan kan je er op de koop toe nog eens bij instellen hoe ver je wil gaan.

In dit specifieke geval is een lusje veel performanter (het wordt dan ook vaak gebruikt als schoolvoorbeeld om aan te tonen dat recursie niet altijd performant is). Maar er zijn veel problemen die je nauwelijks of niet meer met enkel while lussen kan oplossen. Bv een boomstructuur maken van directories/bestanden en onderliggende directories/bestanden is enorm makkelijk op te lossen met recursie, wil je dit gaan lussen dan ga je stoppen met hoofdpijn.

[PeterPan]

Wablief? Nou is het voorbeeld van TS nogal een lelijke functie, maar als je vindt dat recursie om problemen vraagt, zou ik graag een 'minder problematische' oplossing zien dan:

Code: Selecteer alles

int Fibonacci( int n )

{

  if (n<3) return 1;

  return Fibonacci(n-1) + Fibonacci(n-2);

}

(okee vooruit, behalve

Code: Selecteer alles

#include <math.h>

int Fibonacci( int n )

{

  static const double s5 = sqrt(5);

  return int((pow(1+s5,n)-pow(1-s5,n))/(pow(2,n)*s5));

}

dan)

De eerste code is exponentieel, dus ongeschikt.

De tweede code is (al lijk dat wel zo) niet gechikt.

De rekentijd lijkt van orde

\(\log(n)\)

te zijn, maar is dat niet.

Door afrondfouten moeten steeds meer decimalen meegenomen worden.

Dé manier om efficient

\(F_n\)

te berekenen (

\({\cal O}(\log(n))\)

)

is door gebruik te maken van de volgende formule

\(\left(\begin{array}{cc}F_{n+1} & F_n \\F_n & F_{n-1} \end{array} \right) = \left(\begin{array}{cc}1 & 1 \\1 & 0 \end{array} \right)^n\)

[jhnbk]

Dé manier om efficient

\(F_n\)

te berekenen (

\({\cal O}(\log(n))\)

)

is door gebruik te maken van de volgende formule

\(\left(\begin{array}{cc}F_{n+1} & F_n \\F_n & F_{n-1} \end{array} \right) = \left(\begin{array}{cc}1 & 1 \\1 & 0 \end{array} \right)^n\)

Leuke methode. Ik neem aan dat op die matrix dan handiger geschreven wordt zodat die n-de macht makkelijker wordt?

EDIT: uiteraard kan de n-de macht ook met een minimum aan bewerkingen worden gedaan.

[PeterPan]

Die n-de macht reken je recursief uit met de Divide and conquer methode.

Schrijf de n-de macht

\([n]\)

als

\([n] = [\frac{n}{2}]^2\)

als n even en

\([n] = [\frac{n-1}{2}]^2[1]\)

als n oneven.

[jhnbk]

Zulke methode had ik inderdaad in gedachte.

[Rogier]

De tweede code is (al lijk dat wel zo) niet gechikt.

De rekentijd lijkt van orde

\(\log(n)\)

te zijn, maar is dat niet.

Door afrondfouten moeten steeds meer decimalen meegenomen worden.

Vandaar de

\({\cal O}(\log(n))\)

toch?

Maar dan nog, dat lijkt me geen valide argument, want jouw manier zal eveneens met meer digits moeten rekenen naarmate n groter wordt.

Die omschrijving van de divide and conquer methode volg ik niet helemaal. Kun je een praktisch voorbeeld geven, of kun je het algorithme om F_n op die manier te berekenen hier (in eenvoudige pseudocode) posten?

[PeterPan]

Het gaat niet om het aantal digits. Dat is niet relevant.

Het gaat om de berekening van

\(\sqrt{5}\)

in zijn decimalen.

Door de afronding van dit getal en het verheffen van dat getal tot grote machten spelen de afrondingen een zodanige rol dat er steeds meer decimalen nodig zijn. De theorie daaromtrent is iets te veel van het goede om hier precies uit de doeken te doen.

Hier de pseudocode:

int Matrix[2][2] = {{1,0}{0,1}}

int fib(int n)

{

matrixpower(n-1);

return Matrix[0][0];

}

void matrixpower(int n)

{

if (n > 1)

{

matrixpower(n/2);

Matrix = Matrix * Matrix;

}

if (n is odd)

{

Matrix = Matrix * {{1,1}{1,0}}

}

}

[Rogier]

Het gaat niet om het aantal digits. Dat is niet relevant.

Het gaat om de berekening van

\(\sqrt{5}\)

in zijn decimalen.

Door de afronding van dit getal en het verheffen van dat getal tot grote machten spelen de afrondingen een zodanige rol dat er steeds meer decimalen nodig zijn. De theorie daaromtrent is iets te veel van het goede om hier precies uit de doeken te doen.

Ik ben toch wel benieuwd

In de praktijk komt namelijk heel die

\(\sqrt{5}\)

in de berekening nergens voor.

Dit aangezien

\((1\pm\sqrt{5})^n\)

(met

\(n\in\nn\)

) altijd te schrijven is als

\(a\pm b\sqrt{5}\)

met

\(a,b\in\nn\)

, en a en b worden bepaald met louter integerberekeningen (ook hier wat divide en conquer achtige truukjes).

En doordat je

\((a+b\sqrt{5})-(a-b\sqrt{5})\)

neemt hou je

\(2b\sqrt{5}\)

over, dat deel je door

\(2^n\sqrt{5}\)

dus dat komt neer op

\(b/2^{n-1}\)

= b>>(n-1)

Hier de pseudocode:

Ah, nice

Interessant, als ik wat tijd heb ga ik toch ff kijken welke sneller is