Alt0.nl

Na nog wat proberen van Patrick Smits blijkt dat de functie nog korter kan.

unsigned long long fibonacci_list(int reset)
{
    static unsigned long long a=0, b=0;
    if (reset!=0) { a=0; b=0; }
    return (((a+b)==0) ? a++ :
              ((b==0) ? (b+=a--) :
              ((a<b) ? (a+=b) : (b+=a))));
}

Of je er veel aan hebt is een tweede, wat blijkt, de meest simpele iterratieve implementatie is de snelste. Dit komt onder meer doordat ‘ifs’ duur zijn qua tijd, en omdat de simpele versie veel beter te optimaliseren is voor de compiler.

unsigned long long fibonacci_n(int n)
{
    unsigned long long a = 0, b = 1, t;
    int i;

    if (n <= 0) { return (0); }

    for (i = 0; i < (n - 1); i++)
    {
        t = b;
        b = a + b;
        a = t;
    }

    return (b);
}

Zie ook LiteratePrograms.

Maar dan blijft er nog 1 probleem over.. het getal wordt erg snel erg groot, en past dan niet meer in een ‘unsigned long long’. Dan kun je twee dingen doen.

Je kunt zelf iets verzinnen om te rekenen met grotere getallen, maar simpeler is het om een andere programmeer taal te gebruiken, zoals bijvoorbeeld Python.
Hoe meer geheugen je computer heeft, hoe grotere getallen je dan kunt uitrekenen, vrijwel net zo snel als in C.

Was alles maar zo eenvoudig op te lossen.

Normaal gesproken wordt een Fibonacci reeks gedaan met behulp van recursie, als volgt:

unsigned long long fibonacci(int n)
{
    if (n <= 0) { return (0); }
    if (n <= 2) { return (1); }

    return (fibonacci(n-1) + fibonacci(n-2));
}

Naar aanleiding van een simpele Fibonacci reeks functie grotendeels gemaakt door Patrick Smits, kan dit een stuk sneller, zonder recursie, maar met itteratie.

unsigned long long fibonacci_list(int reset)
{
    // Zie je wel Albert Mietus, je hebt slechts 2 variabelen nodig 
    static unsigned long long a=0, b=0;
    if (reset!=0) { a=0; b=0; }
    return ((a==0) ? ((b==0) ? a++ : ++a)
                   : ((b==0) ? (b+=a--) : ((a<b) ? (a+=b) : (b+=a))));
}

unsigned long long fibonacci_first(void)
{
    return (fibonacci_list(1));
}

unsigned long long fibonacci_next(void)
{
    return (fibonacci_list(0));
}

unsigned long long fibonacci(int n)
{
    unsigned long long f = fibonacci_first();

    int i;
    for (i = 1; i <= n; i++) { f = fibonacci_next(); }

    return (f);
}