Comments: 
 From: lx 20080513 06:50 am (UTC)
Haha!  (Link)

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
f_{n} = (((1+sqrt(5))/2)^{n}  ((1sqrt(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:
f_{n} = 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: lindseykuper 20080513 08:03 am (UTC)
Re: postmidnight speculation  (Link)

Yep! You could use that formula and use fastexpt to do the exponentiation with the successivesquaring 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. :)  