"The worst algorithm in the world?"

[mynegation]

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.

[stralep]

Actually, you need just Z ring enriched (if this is right word) with sqrt(5). So instead of one float, you use pair of integers of arbitrary precision. So

(a,b)+(c,d) = (a+c,b+d)

(a,b)/sqrt(5) = (b,a/5)

(a,b)(c,d) = (ac+5bd,ad+bc)

2phi = (1,1)

F(n) = (2phi^n - (2-2phi)^n)/(2^n*sqrt(5))

[edit] As ot said, the right word is "extended"

[shasta]

Given the precision needed in the arithmetic, I've always wondered if the matrix exponentiating method wouldn't be faster. I've never been motivated enough to actually research it, test it, or think hard about it though...

[robinhouston]

I’d love to see an exact algorithm using the closed form formula. It’s obviously possible to do — though it seems fairly complicated — but would it really be faster? My instinct is that it would be slower: if anyone wants to prove me wrong, I’d be thrilled!

(The asymptotic complexity is surely the same, in any case.)

[mccutchen]

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.

[sevenproxies]

Typical way to gain views and make it look like you know what you are talking about (although the author does seem to know good algorithm development). Hell, comparing it to Bogosort is a stretch. Bogosort is not even a naive algorithm.

[perlgeek]

> 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...

[robinhouston]

Bogosort terminates with probability 1. Is it really reasonable to say it doesn’t guarantee termination? People often do say that about randomised algorithms, which confuses me a little. Probability 1 is as guaranteed as anything probabilistic can reasonably hope to be, isn’t it?

[Edited to add: thanks for the replies. I think I expressed myself poorly here. It’s not that I don’t understand the difference between “with probability 1” and “always”. What I mean is that I don’t understand why people sometimes make a big deal out of it, and say “that algorithm is not even guaranteed to terminate” as though that somehow means the algorithm is untrustworthy or useless. The trouble with the game “roll a die until you get 100 sixes in a row” is that it has an astronomical expected running time – not that it might _never_ end, but that it will almost certainly take a very long time.]

[qntm]

I always find it incredibly difficult to concentrate on comparisons of Fibonacci sequence algorithms when I know for a fact that there is a closed-form expression[1] which gives F(n) in constant time.

[1] http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_ex...

[Peaker]

Raising something to the power of n is not constant time.

[_delirium]

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.pdf

[ubasu]

It seems the author hasn't read SICP:

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html...

[TheBoff]

I don't think you've read the article, actually.

The key point is that he is trying to calculate arbitrarily large fibonacci numbers, and so the addition is itself an O(n) operation. This means that even after memoization, the complexity is still O(n^2), and he uses a number of tricks to reduce that.

[snissn]

similarly http://www.cs.berkeley.edu/~vazirani/algorithms/chap0.pdf

[TheBoff]

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!

[mwbiz]

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.

[eru]

But the single request will still be faster. Try it.

[michaelcampbell]

I always liked the sort where you randomize the elements, check to see if they're sorted, and if not try again.

[ginkgo]

My personal favorite has always been permutation sort, where you try all possible permutations of a sequence and check if it is sorted.

What's nice about it is that it is deterministic yet ridiculously slow.

It can also be really easily implemented in Prolog[1] where you simply define what a permutation and being sorted means. After that you just search for a sorted permutation.

[1] http://rosettacode.org/wiki/Sorting_algorithms/Permutation_s...

[cmaggard]

Yeah, I recalled the name as random sort, and was pleasantly surprised when the bogosort link directed to the same algorithm. I particularly enjoyed the "Quantum Bogosort" algorithm on the Wiki page.

http://en.wikipedia.org/wiki/Bogosort#Quantum_bogosort

[masterzora]

I never understood why Bogosort made the check so efficient; it seems so silly. Fortunately, somebody solved this problem and made bogobogosort: http://www.dangermouse.net/esoteric/bogobogosort.html

[samuel]

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...

[georgieporgie]

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.

[robinhouston]

Sorry.

I think it’s only the jargon that’s confusing you. As long as you can remember (or look up) the definition of matrix multiplication, then it genuinely is easy to verify.

  [ fib(n-1) fib(n)   ] x [0 1]
  [ fib(n)   fib(n+1) ]   [1 1]
  
  = [ fib(n)   fib(n-1)+fib(n) ]
    [ fib(n+1) fib(n)+fib(n+1) ]
  
  = [ fib(n)   fib(n+1) ]
    [ fib(n+1) fib(n+2) ]

[ignifero]

Interesting writeup, thanks. OT: For all its fame, has any of you ever needed to calculate Fibbonacci numbers in real life? I haven't.

[fhars]

And neither am I a member of the Fibonacci Association http://www.mathstat.dal.ca/fibonacci/ http://www.fq.math.ca/

[Edit:] But there are some interesting data structures based on them: http://en.wikipedia.org/wiki/Fibonacci_heap

[te_platt]

It seems like I had to as part of an interview once. Still, I have needed to write recursive functions many, many times and it's good to review some of what can go wrong.