Alt0.nl

Weer eens wat anders. Ik werk nu aan een open source produkt, betaald door mijn werkgever JVH.

Het is (of beter gezegd, wordt) een set van GNU Make compatible Makefiles, die je kunt gebruiken om je software op- en voor verschillende platformen te bouwen. En dit alles, zonder dat je al te veel hoeft af te weten van Makefiles.

Meer informatie is te vinden op JUM Uses Make.

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

Als je je graag met een IDE werkt, en je programmeert in C of C++, dan is CodeLite een aanrader.

Het programma is nog volop in ontwikkeling, maar ziet er al veelbelovend uit.
Het werkt stukken sneller dan Eclipse en Visual Studio, en ondersteunt meer dan genoeg voor de meeste (hobby) programmeurs.

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