12 ms·
"The worst algorithm in the world?"
- mccutchen 15y agoThe 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 15y agoTypical 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.
- nandemo 15y agoFWIW, in my Programming Languages Theory class the first sorting algorithm we learned for Prolog was Permutation sort, which is a better version of Bogosort. Instead of trying a random permutation each time, Permutation sort will try each permutation once. In Prolog, this is a (the?) naive sort. The code below consists of declaring that S is a sorted version of L as long as S is a permutation of L and S is sorted. permutation_sort(L,S) :- permutation(L,S), sorted(S). sorted([]). sorted([_]). sorted([X,Y|ZS]) :- X =< Y, sorted([Y|ZS]). permutation([],[]). permutation([X|XS],YS) :- permutation(XS,ZS),select(X,YS,ZS).
- sevenproxies 15y agopermutation([X|XS],YS) :- permutation(XS,ZS),select(X,YS,ZS). Where is ZS defined? Bear in mind that I only took half a module's worth (6 modules in a year at my university) of Prolog and we really just used it for learning predicate logic. Nevertheless, using Prolog (especially when my code worked!) blew my mind. In the assignment I had to write a program that mimicked part of an aircraft controller in that each aircraft in it's flightplan had to be separated from all other aircraft. Do you think Prolog will ever become popular (perhaps with the incoming Semantic web) or is it destined for academic work and system proofs only?
- sesqu 15y agoZS is defined by select. I don't believe Prolog will become any more popular than it is. The Japanese had some sort of a government project a few years ago, but I think that fell through. Now we have Erlang, Haskell and Java libraries that replicate most functionality, and then some.
- ignifero 15y agoInteresting writeup, thanks. OT: For all its fame, has any of you ever needed to calculate Fibbonacci numbers in real life? I haven't.
- te_platt 15y agoIt 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.
- fhars 15y agoAnd neither am I a member of the Fibonacci Association http://www.mathstat.dal.ca/fibonacci/ http://www.mathstat.dal.ca/fibonacci/ http://www.fq.math.ca/ http://www.fq.math.ca/ [Edit:] But there are some interesting data structures based on them: http://en.wikipedia.org/wiki/Fibonacci_heap http://en.wikipedia.org/wiki/Fibonacci_heap
- arethuza 15y agoThanks - I was struggling to remember where I had heard of a practical application of the Fibonacci sequence in CS. The Fibonacci Heap was it - I'm pretty sure it was mentioned on my CS course and it must have been '87, same year it was published!
- michaelcampbell 15y agoI always liked the sort where you randomize the elements, check to see if they're sorted, and if not try again.
- cmaggard 15y agoYeah, 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 http://en.wikipedia.org/wiki/Bogosort#Quantum_bogosort
- arethuza 15y agoIf you enjoyed that you might like the novel Quarantine by Greg Egan: http://en.wikipedia.org/wiki/Quarantine_%28Greg_Egan_novel%29 http://en.wikipedia.org/wiki/Quarantine_%28Greg_Egan_novel%2...
- ginkgo 15y agoMy 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_sort#Prolog http://rosettacode.org/wiki/Sorting_algorithms/Permutation_s...
- masterzora 15y agoI 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 http://www.dangermouse.net/esoteric/bogobogosort.html
- samuel 15y agoDunno. 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...
- ubasu 15y agoIt seems the author hasn't read SICP: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.2 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html...
- snissn 15y agosimilarly http://www.cs.berkeley.edu/~vazirani/algorithms/chap0.pdf http://www.cs.berkeley.edu/~vazirani/algorithms/chap0.pdf
- TheBoff 15y agoI 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.
- ubasu 15y agoHis way around that is to use the matrix recurrence relation, which is also there in SICP as an exercise. But it's a nice discussion in any case.
- perlgeek 15y ago> 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_rounding http://en.wikipedia.org/wiki/Fibonacci_number#Computation_by...
- robinhouston 15y agoBogosort 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.]
- unignorant 15y agoThere is a distinction between "surely" and "almost surely": http://en.wikipedia.org/wiki/Almost_surely http://en.wikipedia.org/wiki/Almost_surely Bogosort almost surely terminates.
- vog 15y agoProbability 1 is as guaranteed as anything probabilistic can reasonably hope to be, isn’t it? Unfortunately, it isn't. This is the reason why in mathematics, we say that "possibility 1" means that an event is "almost sure", which is different from a "sure" event. For instance, you can play a game where you roll a dice over an over again. You win if you get 100 times a 6 in sequence. If you play this game without any time limit, your possibility to win is exactly 1, which means that you can be "almost sure" you'll win in the end. However, you can't be sure, because there is still the possibility that you don't get 100 times a 6 in an eternity. Note that this only happens in infinite probability spaces. In finite spaces, "almost sure" and "sure" are equivalent. Also note that the same holds for "probability 0" which means "almost impossible", not to be confused with "impossible".
- _delirium 15y agoIn 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 http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
- mwbiz 15y agoIf 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 15y agoBut the single request will still be faster. Try it.
- mynegation 15y agoVery 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_expression 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.
- shasta 15y agoGiven 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 15y agoI’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.)
- kenjackson 15y ago(The asymptotic complexity is surely the same, in any case.) The closed form complexity is not the same (not sure how it could be). Here's the code written in standard most language psuedocode: fib(n) { double c = 1.6180339887; return round((power(c, n) - power(1-c, n))/sqrt(5)); } Note: I assume your point wasn't that computing the golden ratio exactly is... well ummm... time consuming.
- robinhouston 15y agoActually I think that roughly was my point. :-) You can’t get an exact answer in general by using fixed-size floating-point numbers, as your pseudocode does. The number of bits of precision you need to get an exact answer is going to depend on the input value, presumably linearly.
- georgieporgie 15y agoThis 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 15y agoSorry. 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) ]
- TheBoff 15y agoPpffftt, 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!
- deleted 15y ago[deleted]
- qntm 15y agoI 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_expression http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_ex...
- Peaker 15y agoRaising something to the power of n is not constant time.