On the Linear Time Algorithm For Finding Fibonacci Numbers

You're replying to a comment by Ray.

Ray Permalink
July 07, 2009, 18:05

Zach, you're also just plain wrong. 128-bit integers only get you up to around f(200) or so (too lazy to calculate the exact number of bits, but it's close). Fibonacci numbers are *big*.

Anyway, any decent implementation will have a short linear part at the beginning, and then an n^2 part after that.

Unless, of course, you can play tricks to get your computation time down to constant again. No existing processor can do this, but a processor that had a configurable number of bits could stay linear for as long as it had computation units. Again, difference between theory and practice.

Reply To This Comment

(why do I need your e-mail?)

(Your twitter handle, if you have one.)

Comment Help

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

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