[deleted]
"The worst algorithm in the world?"
61–70 of 73 posts
Re: "The worst algorithm in the world?"
#62The 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.
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.
FWIW, 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 =Re: "The worst algorithm in the world?"
#63> 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:/…
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 “…
If you talk about O(something(n)) run times there's an implicit agreement that you are talking about worst case behavior.
And the worst case of bogosort is not to terminate.
Re: "The worst algorithm in the world?"
#64Earlier quoted context omitted.
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 “…
If you talk about O(something(n)) run times there's an implicit agreement that you are talking about worst case behavior. And the worst case of bogosort is not to terminate.
Not sure about that: qick sort is generally said to be O(NlogN), but its worst case is O(N^2) (the simple implementation anyway).
Re: "The worst algorithm in the world?"
#65I 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...
Re: "The worst algorithm in the world?"
#66I 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...
Raising something to the power of n is not constant time.
Re: "The worst algorithm in the world?"
#67Earlier quoted context omitted.
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 “…
Probability 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…
Your example is misleading, because the same can be said about the game where you roll a dice over and over again, and you win if you get a 6.
The probability that the game ends is 1, but it is not guaranteed to end. Yet no reasonable person will worry about this in practice.
Your example with 100 times 6 in a row is conceptually exactly the same, just the expected time until the game terminates is much, much larger.
Re: "The worst algorithm in the world?"
#68Very 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.
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) = (a c+5 b d,a d+b c) 2phi = (1,1) F(n) = (2phi^n - (2-2phi)^n)/(2^n*sqrt(5)) [edit] As ot said, the right word is "extended"
I did this once for a Project Euler question. I called the function "awful-thing". It worked.
;this calculates (a+b√sqr)^n, using exponentiation by squaring
(def awful-thing (n a b sqr)
(afnwith (n n i a r b it 1 rt 0)
(if (is n 0)
(list it rt)
(even n)
(self (/ n 2)
(+ (square i) (* sqr (square r)))
(* 2 i r)
it
rt)
(self (- n 1)
i
r
(+ (* i it) (* sqr r rt))
(+ (* i rt) (* r it))))))
(def fib (n)
(with (pow2 (expt 2 n)
hh (map - (awful-thing n 1 1 5) (awful-thing n 1 -1 5)))
;now hh = '(a b) where (fib n) = (a + b*root5)/(root5*pow2)
;a should = 0
(/ (cadr hh)
pow2)))Re: "The worst algorithm in the world?"
#69Earlier quoted context omitted.
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.
FWIW, 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. pe…
permutation([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?
Re: "The worst algorithm in the world?"
#70Earlier quoted context omitted.
If you talk about O(something(n)) run times there's an implicit agreement that you are talking about worst case behavior. And the worst case of bogosort is not to terminate.
Not sure about that: qick sort is generally said to be O(NlogN), but its worst case is O(N^2) (the simple implementation anyway).
That's an abuse of notation. Quicksort is expected O(N log N), where the expectation is usually over a uniform distribution of all permutations.
The actual notation for proportional asymptotic dominance of expectation is too convoluted for use, so people just don't use one. But to even leave out the word "expected" is just plain wrong.