gistfile1.c

// O(1) in both time and space
unsigned fibonacci(unsigned n)
{
    double s5 = sqrt(5.0);
    double phi = (1.0 + s5) / 2.0;

    double left = pow(phi, (double)n);
    double right = pow(1.0-phi, (double)n);

    return (unsigned)((left - right) / s5);
}