HNGlance

Top Best New Show

How to compute Fib(n) in log(n) time

http://jliszka.livejournal.com/38105.html

by Xichekolas • 17 years ago

2 2 17 years ago

JL

jliszka.livejournal.com

Related Stories

Loading related stories...

Comments

2

cperciva• 17 years ago

Correction: This computes Fib(n) in O(n log n log log n) time given a fast integer multiplication.

Xichekolas• 17 years ago

Yeah, it's only logarithmic in the number of matrix multiplications, so the title is a bit hyperbolic, but I just thought the technique was cool.

I got there via: http://blog.sigfpe.com/2008/11/approach-to-algorithm-paralle...

Which was perhaps more informative as to the actual technique, but had less obvious wow factor. My bad.

Source preview

jliszka.livejournal.com

HNGlance

© 2024-2026 HN Glance. Story content belongs to its original sources.

Privacy
Terms