No account? Create an account
 I can't stop thinking about Fibonacci numbers! - Lindsey Kuper [entries|archive|friends|userinfo]
Lindsey Kuper

 [ website | composition.al ] [ userinfo | livejournal userinfo ] [ archive | journal archive ]

I can't stop thinking about Fibonacci numbers! [May. 12th, 2008|11:11 pm]
Lindsey Kuper
 [ Tags | programming ]

No, really, I can't!

From:
2008-05-13 06:50 am (UTC)

### Haha!

If you only knew!
From:
2008-05-14 02:25 am (UTC)

### Re: Haha!

I think I might know.
From:
2008-05-13 07:42 am (UTC)

### post-midnight speculation

One of the mind blowing mathematical facts I remember learning at some point in college was that there's a closed form for the Fibonacci sequence. It's

fn = (((1+sqrt(5))/2)n - ((1-sqrt(5))/2)n)/sqrt(5).

That second term has an absolute value less than 0.5 for all n greater than 1, so you can reduce it to:

fn = round(((1+sqrt(5))/2)n / sqrt(5)) when n>1

I wonder if that might somehow yield a faster way to compute large Fibonacci numbers, or if the square roots and exponentiation would be even slower than conventional approaches.
From:
2008-05-13 08:03 am (UTC)

### Re: post-midnight speculation

Yep! You could use that formula and use `fast-expt` to do the exponentiation with the successive-squaring trick. It wouldn't end up better than O(log n), though. But I bet it's faster than my algorithm at least some of the time (like if n is a power of 2).