You're replying to a comment by John Fremlin.

July 08, 2009, 05:36

Hi Cantonmat,

I looked at this a while ago because I was annoyed about stupid implementations of Fibonacci. I quickly noticed that the value of Fn quickly overflows fixed precision datatypes so as you point out you can't use fixed precision arithmetic and have to take account the non-trivial complexity of your operations.

I looks at the real complexity for Binet's formula and implement the better identity used by GMP
F2k = (Fk+1)^2 − (Fk−1)^2

Glimpses of Lisp: Fibonacci and the Netflix prize

Reply To This Comment

(why do I need your e-mail?)

(Your twitter handle, if you have one.)

Type the word "computer_147": (just to make sure you're a human)

Please preview the comment before submitting to make sure it's OK.