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).
De lamme manier zou zo gaan: (dit is zonder binaire truukjes)Nu ben ik toch wel zeer benieuwd naar die trucjes. Overtuig me. Ik heb er een hard hoofd in
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);
}Welke beide methodes? De matrix manier van PeterPan en die@Rogier: zeker beiden eens vergelijken en hier laten weten ! Ik kan met beide methodes in GNU Octave geen significant verschil vinden.
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, 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.
Uiteraard, dat wordt gewoon een int[4].@rogier: wat betreft die pseudocode betreft zou ik geen 2D-array nemen
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);
}Met Lanczos.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?
PeterPan schreef:@Rogier. Je code is duidelijk van orde\(n\)Lijkt me hetzelfde als for(p=1; p<2log(n); p++)Code: Selecteer alles
int p = 1; while(p<=n) // p = 2^(hoeveelste bit) { (...) p += p; }
Op iedere plek waar je matrixvermenigvuldiging toepast is dat aan de orde. Maar het kan natuurlijk prima met een arraytje met 4 elementen.In mijn pseudocode komt slechts 1 matrixje voor van orde 2x2. Zo erg kan dat niet zijn.
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];
}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.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
AangezienIk 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
Maar vergeet ook niet dat dat allemaal met constante limieten is, dus een béétje compiler optimized dat er allemaal uit.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
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;
}
}Code: Selecteer alles
int nn = m*n;
int[] arr = int[nn];
for(int i = 0; i < nn; i++) {
arr[i] = i;
}
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!De volgende code zal niet langzamer zijn dan de door jouw helemaal uitgeschreven code.
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;
}