|I can't stop thinking about Fibonacci numbers!
||[May. 12th, 2008|11:11 pm]
No, really, I can't!
2008-05-13 06:50 am (UTC)
If you only knew!
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.
2008-05-13 08:03 am (UTC)
Re: post-midnight speculation
Yep! You could use that formula and use
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).
I'm thinking I might talk about this at Code n' Splode, if y'all can stomach a math talk. Gabrielle wants me to talk about something, and I'm not sure I have anything interesting to say about anything that is not an integer sequence.
Personally, I would adore a math talk! And you have plenty that is interesting to say. I'd say pick a topic you know you've geeked out on, or worked on, or something and go from there. I'm having writer's block about mine too for this month, but I've got a bit of material already, so I guess if nothing else the tales from the pit could be reaaaaally short. :)