On the implementation of the Fibonacci seq.

We all enjoy showing off how elegant our implementation of the Fibonacci sequence is in Haskell or Scheme or whatever.  But, frankly, they suck.  Even if you're using tail recursion to avoid fucking up the stack it's still terribly inefficient.

Here is the correct way to implement the Fibonacci sequence (in Scheme):
(define (fibonacci x)
    (let  ((phi (/ (+ 1 (sqrt 5)) 2)))
    (+ (/ (+ (expt phi x) (expt (- 1 phi) (- x 2))) (+ (expt phi 2) 1)) (/ (- (expt phi (- x 1)) (* phi (expt (- 1 phi) (- x 2)))) (+ (expt phi 2) 1)))))

>>18
You can port that whereever you have floating point maths, at least. What's wrong with lookup tables anyway? Given the limited valid input range, the memory use is neglible, and even if you generate it dynamically, the difference between O(1) vs. O(n) neglible.