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

>>22,23
An bog-standard iterative fibonacci function written in Python gives accurate results instantly on my machine for n up to about 20000. (After that it still gives accurate results, but there is a noticable delay before printing the answer, probably because of terminal scrolling.)
Given a "O(1)" implementation that only works up to n = 1474 (as tested with guile), I'd say the difference between O(1) and O(n) is pretty darn negligible.