by mynegation on 5/11/11, 8:58 PM
Very good demonstration of subsequent improvements of a naive algorithm. To me that was somewhat depreciated by the fact that you can actually calculate n-the Fibonacci number using Binet's closed form formula (
http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_ex...). You will need arbitrary precision arithmetic starting with certain 'n' though, as IEEE 754 will not give you correct result.
by mccutchen on 5/11/11, 6:56 PM
The title is hyperbole (I'm sure that I've written much, much worse algorithms, many times), but the breakdown of Fibonacci sequence algorithms is really enjoyable.
by perlgeek on 5/11/11, 8:31 PM
> It’s not just bad in the way that Bubble sort is a bad sorting algorithm; it’s bad in the way that Bogosort is a bad sorting algorithm.
Nonono, Bogosort is way worse than naive recursive fibonacci - the former doesn't even guarantee termination, recursive fibonacci still does.
If you want to calculate fibonacci numbers not as a misguided exercise in algorithms but actually efficiently, use an algebraic form: http://en.wikipedia.org/wiki/Fibonacci_number#Computation_by...
by qntm on 5/12/11, 10:10 AM
by _delirium on 5/11/11, 8:33 PM
In a somewhat similar genre, I enjoyed this paper on computing primes, and some of the very-inefficient algorithms that have been used for such purposes (often mislabeled as the "sieve of Eratosthenes"):
http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdfby ubasu on 5/11/11, 8:23 PM
by TheBoff on 5/11/11, 11:46 PM
Ppffftt, I wrote a recursive algorithm that calculates 2^n in O(2^n) time for an exam question.
That's what I call a bad algorithm!
by mwbiz on 5/11/11, 8:39 PM
If you're writing in JavaScript it's a nice candidate for self memoizing functions. Obviously this is only helpful if you're making numerous requests to the method, a single request still produces a series of recursive calls.
by michaelcampbell on 5/11/11, 7:48 PM
I always liked the sort where you randomize the elements, check to see if they're sorted, and if not try again.
by samuel on 5/11/11, 8:03 PM
Dunno. IIRC Every time I have seen the "bad" Fibonacci recursive algorithm has been followed by the "good" recursive one (bottom-up), which is O(1) in size if your language/implementation does tail-call elimination...
by georgieporgie on 5/11/11, 9:30 PM
This started out taking baby steps, then took a huge leap in complexity right here:
Since the Fibonacci numbers are defined by a linear recurrence, we can express the recurrence as a matrix, and it’s easy to verify that...
It's been way too long since my math minor for me to understand that.
by ignifero on 5/11/11, 7:27 PM
Interesting writeup, thanks. OT: For all its fame, has any of you ever needed to calculate Fibbonacci numbers in real life? I haven't.