As pointed out above - the most efficient to compute large fibonacci numbers is to compute the matrix power [[1,0],[1,1]]^n using repeated squaring. Or you could use the known identities to compute Lucas numbers, which amount to the same thing. The lispmath talks about computing fib(40000) in 100..200 ms, the repeated squaring approach computes the same number in < 5 ms (on my not very powerful machine).