sciencetalk

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

Nu ben ik toch wel zeer benieuwd naar die trucjes. Overtuig me. Ik heb er een hard hoofd in

@Rogier: zeker beiden eens vergelijken en hier laten weten ! Ik kan met beide methodes in GNU Octave geen significant verschil vinden.

Nu ben ik toch wel zeer benieuwd naar die trucjes. Overtuig me. Ik heb er een hard hoofd in

De lamme manier zou zo gaan: (dit is zonder binaire truukjes)

Code: Selecteer alles

int Fib( int n )

{

int a=1, b=1; // staat voor a+b√5

for (int i=1; i<n; i++) // n keer met 1+√5 vermenigvuldigen

{

int new_a += 5*b;

b += a;

a = new_a;

}

// a+b√5 is nu (1+√5)^n

return b >> (n-1);

}

Ik pruts nog even met een optimized versie, maar ik heb een donkerbruin vermoeden dat er een verrassend resultaat uit komt!

@Rogier: zeker beiden eens vergelijken en hier laten weten ! Ik kan met beide methodes in GNU Octave geen significant verschil vinden.

Welke beide methodes? De matrix manier van PeterPan en die

\(\left((1+\sqrt{5})^n-(1-\sqrt{5})^n\right)/(2^n\sqrt{5})\)

die ik noemde? (die laatste dus echt wiskundig uitgerekend, met wortels en machten enzo)

@rogier: wat betreft die pseudocode betreft zou ik geen 2D-array nemen, zelf met optimalisaties van de compiler gaat dit nog steeds zeer traag, zo heb ik eens zelf een matrix-oplos-programma gebouwd dat d.m.v. LU-decompositie een vierkante matrix kun uitwerken, en waarbij ik de matrices intern als een 1D-array voorstelde. Een 50x50 matrix werd opgelost in 0.0003 sec. tijd. (dat zijn dus 2500) element. Dus als je wilt dat het sneller gaat, moet je 1-D lijsten gebruiken, en zoveel mogelijk vermenigvuldigingen omzetten naar optellingen.

Die laatste gewoon numeriek maar jij pakt het iets wiskundiger aan blijkbaar.

@rogier: wat betreft die pseudocode betreft zou ik geen 2D-array nemen, zelf met optimalisaties van de compiler gaat dit nog steeds zeer traag, zo heb ik eens zelf een matrix-oplos-programma gebouwd dat d.m.v. LU-decompositie een vierkante matrix kun uitwerken, en waarbij ik de matrices intern als een 1D-array voorstelde. Een 50x50 matrix werd opgelost in 0.0003 sec. tijd. (dat zijn dus 2500) element. Dus als je wilt dat het sneller gaat, moet je 1-D lijsten gebruiken, en zoveel mogelijk vermenigvuldigingen omzetten naar optellingen.

Even kort off-topic in dit geval. Als ik een vierkante matrix A heb (groot, kan makkelijk meer dan 100x100 zijn) met vrij veel nullen in. Welke methode is dan de snelste om Ax=B op te lossen naar x?

@rogier: wat betreft die pseudocode betreft zou ik geen 2D-array nemen

Uiteraard, dat wordt gewoon een int[4].

Die van mij heb ik momenteel zo: (kan nog wel sneller)

Code: Selecteer alles

int Fib( int n )

{

int a=1, b=0; // staat voor "a+b√5"

int x=1, y=1;

int p = 1;

while(p<=n) // p = 2^(hoeveelste bit)

{

if (n&p)

{

// (a+b√5) = (a+b√5)*(x+y√5)

int a1 = a;

a = a*x+5*b*y;

b = a1*y+b*x;

}

// (x+y√5) = (x+y√5)^2 = (1+√5)^p

int x1 = x;

x = x*x+5*y*y;

y *= 2*x1;

p += p;

}

return b >> (n-1);

}

En die lijkt vooralsnog bijna 3 keer zo snel

Maar ik zal de matrixvariant ook nog wat verder optimizen.

Even kort off-topic in dit geval. Als ik een vierkante matrix A heb (groot, kan makkelijk meer dan 100x100 zijn) met vrij veel nullen in. Welke methode is dan de snelste om Ax=B op te lossen naar x?

Met Lanczos.

@Rogier. Je code is duidelijk van orde

\(n\)

(n-loop). Dat is nog lang niet van orde

\(\log(n)\)

.

Je code kan voor kleine n-waarden sneller zijn, maar niet voor grote waarden.

@Vladimir Lenin: In mijn pseudocode komt slechts 1 matrixje voor van orde 2x2. Zo erg kan dat niet zijn.

PeterPan schreef:@Rogier. Je code is duidelijk van orde
\(n\)
Code: Selecteer alles
int p = 1;

while(p<=n) // p = 2^(hoeveelste bit)

{

(...)

p += p;

}
Lijkt me hetzelfde als for(p=1; p<²log(n); p++)

In mijn pseudocode komt slechts 1 matrixje voor van orde 2x2. Zo erg kan dat niet zijn.
Op iedere plek waar je matrixvermenigvuldiging toepast is dat aan de orde. Maar het kan natuurlijk prima met een arraytje met 4 elementen.

Heel veel sneller dan dit krijg ik die matrix methode denk ik niet:

Code: Selecteer alles

static int matrices[8];

static int a[4];

static int b[4];

void MatrixPower( int n )

{

if (n>1)

{

MatrixPower(n>>1);

// a = a * a

b[0] = a[0];

b[1] = a[1];

b[2] = a[2];

b[3] = a[3];

a[0] = b[0]*b[0] + b[1]*b[2];

a[1] = b[0]*b[1] + b[1]*b[3];

a[2] = b[2]*b[0] + b[3]*b[2];

a[3] = b[2]*b[1] + b[3]*b[3];

}

if (n&1)

{

// a = a * {{1 1}{1 0}}

b[0] = a[0];

b[1] = a[1];

b[2] = a[2];

b[3] = a[3];

a[0] = b[0] + b[1];

a[1] = b[0];

a[2] = b[2] + b[3];

a[3] = b[2];

}

}

int Fib( int n )

{

a[0] = a[3] = 1;

a[1] = a[2] = 0;

MatrixPower(n-1);

return a[0];

}

En als ik die vergelijk met die van mij is de matrixmethode toch zo'n 2.5 keer langzamer.

Indien nog suggesties om een van beide methodes te verbeteren, graag.

Die van mij kan in een hoop gevallen nog wel sneller door slimmer van bitcombinaties gebruik te maken. Bijvoorbeeld

\(x^{15}\)

wordt nu gedaan als

\(x^8x^4x^2x\)

maar dat kan ook met

\((x^5)^3\)

. Wil je dit consistent toepassen dan moet je n opdelen in priemfactoren, en dat gaat niet met

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

, en het is me ook ff teveel gepriegel om dat verder te benutten.

Het vage vermoeden dat ik daarstraks had was dat deze twee methoden, zij het vanuit een compleet verschillende benadering / interpretatie, op dezelfde berekening neerkwamen. Maar dat was niet zo.

Ik vind dat je fraaie oplossing hebt gegeven.

De volgende code zal niet langzamer zijn dan de door jouw helemaal uitgeschreven code.

Verborgen inhoud

PeterPan schreef:Ik vind dat je fraaie oplossing hebt gegeven.

De volgende code zal niet langzamer zijn dan de door jouw helemaal uitgeschreven code.

Verborgen inhoud

Ik ben er van overtuigd van wel, nu het is eenvoudig te testen, geef de 2 algoritmen een opdracht om alle fibonacci-getallen te berekenen tot aan 10.000 bijvoorbeeld, en laat je computer het tijdsverschil bijhouden, ik ben benieuwd.

Bovendien mag je niet vergeten dat je in jouw code een boel onnodige for-lussen gebruikt, en 80% van de rekentijd gaat verloren in organisatievormen als for, while en if

Ik ben er van overtuigd van wel, nu het is eenvoudig te testen, geef de 2 algoritmen een opdracht om alle fibonacci-getallen te berekenen tot aan 10.000 bijvoorbeeld

Aangezien

\(F_{10000} > 10^{2089}\)

kom je er met normale integers en floats niet meer

Maar gewoon heel vaak een kleinere serie herhalen volstaat prima lijkt me.

Bovendien mag je niet vergeten dat je in jouw code een boel onnodige for-lussen gebruikt, en 80% van de rekentijd gaat verloren in organisatievormen als for, while en if

Maar vergeet ook niet dat dat allemaal met constante limieten is, dus een béétje compiler optimized dat er allemaal uit.

Evengoed denk ik dat PeterPan's implementatie wel te veel voor niks doet, ik time beide oplossingen later nog wel ff.

Tja, ik denk dat je nooit al teveel op de expertise van een compiler moet vertrouwen, ze zijn over het algemeen nogal domme logge programma's die uiteraard geen optimalisatie echt zien, een compiler werkt niet algebraïsch stel volgende code:

Code: Selecteer alles

int[,] arr = int[m,n];

for(int i = 0; i < m; i++) {

   for(int j = 0; j < n; j++) {

	  arr[i,j] = i+j;

   }

}

ik geef toe dat een compiler dit misschien nog zou zien, en zou optimaliseren naar

Code: Selecteer alles

int nn = m*n;

int[] arr = int[nn];

for(int i = 0; i < nn; i++) {

   arr[i] = i;

}

als je echter bijvoorbeeld een methode schrijft die een mxn matrix construeert, en vervolgens in een andere methode ga je die array gaan opvullen, dan gaat het a fout. en het kost dus al dubbel zoveel tijd aan organisatie (2 for-lussen). Vervolgens komt daar ook nog bij dat het adres inwendig berekent moet worden (i*n+j) wat uiteraard een vermenigvuldiging bevat en dus veel trager dan een optelling gaat.

De volgende code zal niet langzamer zijn dan de door jouw helemaal uitgeschreven code.

Uitschrijven is vrijwel altijd sneller dan loops. Als je matrixvermenigvuldiging uitschrijft, geef je de compiler meer ruimte om te optimaliseren. Loop unfolding komt niet vaak voor als optimalisatie.

De volgende code zal niet langzamer zijn dan de door jouw helemaal uitgeschreven code.

Helaas, jouw 'compacte' variant was bijna twee keer zo langzaam!

Kan natuurlijk van de compiler afhangen, maar ik gebruik visual studio 8 (enterprise versie, niet de express) met alle optimalisaties aan (en in release mode uiteraard) en die optimaliseert doorgaans toch verbluffend goed.

Maar die matrixmethode kan nog efficiënter. Want aangezien voortdurend geldt M[0][1] = M[1][0] hoef je eigenlijk maar 3 variabelen bij te houden, en die vermenigvuldiging met {{1 1}{1 0}} kan zelfs met een paar simpele optellingen. En door de volgorde wat aan te passen hoef je ook niet eerst de hele matrix te kopiëren.

Efficiënter dan dit kan hij volgens mij niet:

Code: Selecteer alles

static int ma,mb,mc,ma1,mb1; // {{ma mb}{mb mc}} representeert de matrix, ma1 en mb1 zijn temp variabelen

void MatrixPower( int n )

{

if (n>1)

{

MatrixPower(n>>1);

// M = M * M

ma1 = ma;

mb1 = mb;

ma = ma*ma + mb*mb;

mb *= ma1+mc;

mc = mb1*mb1 + mc*mc;

}

if (n&1)

{

// M = M * {{1 1}{1 0}}

ma1 = ma;

mc = mb;

ma += mb;

mb = ma1;

}

}

int Fib( int n )

{

ma = mc = 1;

mb = 0;

MatrixPower(n-1);

return ma;

}

Deze is ongeveer 25% langzamer dan die integer [wortel]5 methode van mij.

sciencetalk

Getallen van Fibonacci berekenen.

Re: Getallen van Fibonacci berekenen.

Re: Getallen van Fibonacci berekenen.

Re: Getallen van Fibonacci berekenen.

Re: Getallen van Fibonacci berekenen.

Re: Getallen van Fibonacci berekenen.

Re: Getallen van Fibonacci berekenen.

Re: Getallen van Fibonacci berekenen.

Re: Getallen van Fibonacci berekenen.

Re: Getallen van Fibonacci berekenen.

Re: Getallen van Fibonacci berekenen.

Re: Getallen van Fibonacci berekenen.

Re: Getallen van Fibonacci berekenen.

Re: Getallen van Fibonacci berekenen.

Re: Getallen van Fibonacci berekenen.

Re: Getallen van Fibonacci berekenen.