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.
"The worst algorithm in the world?"
11–20 of 73 posts
Re: "The worst algorithm in the world?"
#12I always liked the sort where you randomize the elements, check to see if they're sorted, and if not try again.
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...
Re: "The worst algorithm in the world?"
#13Very 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.
Re: "The worst algorithm in the world?"
#14Interesting writeup, thanks. OT: For all its fame, has any of you ever needed to calculate Fibbonacci numbers in real life? I haven't.
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
Re: "The worst algorithm in the world?"
#15Very 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.
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...
Re: "The worst algorithm in the world?"
#16Interesting writeup, thanks. OT: For all its fame, has any of you ever needed to calculate Fibbonacci numbers in real life? I haven't.
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
Thanks - 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!
Re: "The worst algorithm in the world?"
#17I always liked the sort where you randomize the elements, check to see if they're sorted, and if not try again.
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
If you enjoyed that you might like the novel Quarantine by Greg Egan:
http://en.wikipedia.org/wiki/Quarantine_%28Greg_Egan_novel%2...
Re: "The worst algorithm in the world?"
#18It seems the author hasn't read SICP: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html...
Re: "The worst algorithm in the world?"
#19This 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.
Re: "The worst algorithm in the world?"
#20Very 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.
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.)