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);
}

Niet nieuw, niet spannend, niet veel… maar voor diegene die net begonnen is met programmeren in C.

#ifndef FALSE
#define FALSE   (0)
#define TRUE    (!FALSE)
typedef int BOOL;
#endif

#define INSIST(b,m...)  \
        {\
            if(!(b)) \
            { \
                fprintf(stderr,"%s, %d: insist '%s' failed!\n",\
                         __FILE__, __LINE__, #b); \
                fprintf(stderr, m); \
                fprintf(stderr, "\n"); \
                abort(); \
            } \
        }

#define HIGH(x,y)       (((x)>(y))?(x):(y))
#define LOW(x,y)        (((x)<(y))?(x):(y))

#define BIT(x)          (1<<(x))

#define SWAP(x,y)       {x^=y;y^=x;x^=y;}
#define SWAPT(x,y,type) {type tmp=x; x=y; y=tmp;}

#define FREE(m)         {free(m); m = NULL;}

Hoe zet je in nette ansi c code een integer om in een pointer, en vice versa?

#define I2P(i) ((void *)((char *)0 + (i)))
#define P2I(p) ((int)((char *)(p) - (char *)0))

I2P: char adres 0 + integer adres is char adres van i. Cast naar void pointer zodat het resultaat in elke pointer var past.
P2I: cast pointer naar char pointer (kleinste adressering), haal daar char adres 0 vanaf om een integer waarde te verkrijgen. De cast naar int zit er bij omdat je in c in principe altijd het beste int kunt gebruiken, dat is op elk systeem het snelste type.