Log in

No account? Create an account
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

No, really, I can't!


[User Picture]From: lx
2008-05-13 06:50 am (UTC)


If you only knew!
(Reply) (Thread)
[User Picture]From: lindseykuper
2008-05-14 02:25 am (UTC)

Re: Haha!

I think I might know.
(Reply) (Parent) (Thread)
[User Picture]From: stereotype441
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.
(Reply) (Thread)
[User Picture]From: lindseykuper
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).
(Reply) (Parent) (Thread)
[User Picture]From: stacy_bird
2008-05-14 01:56 am (UTC)
Man, I love you.
(Reply) (Thread)
[User Picture]From: lindseykuper
2008-05-14 02:23 am (UTC)
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.
(Reply) (Parent) (Thread)
[User Picture]From: stacy_bird
2008-05-14 02:35 am (UTC)
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. :)
(Reply) (Parent) (Thread)