Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

"The worst algorithm in the world?"

bosker.wordpress.com

Post reply on HN
Print view View original

21–30 of 73 posts

Re: "The worst algorithm in the world?"

#21

Post by robinhouston »

perlgeek wrote: post #9

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

Re: "The worst algorithm in the world?"

#22

Post by robinhouston »

georgieporgie wrote: post #19

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.

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) ]

Re: "The worst algorithm in the world?"

#23

Post by masterzora »

michaelcampbell wrote: post #5

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

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

Re: "The worst algorithm in the world?"

#24

Post by kenjackson »

robinhouston wrote: post #20
mynegation wrote: post #13

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.

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

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

Re: "The worst algorithm in the world?"

#25

Post by unignorant »

robinhouston wrote: post #21
perlgeek wrote: post #9

> 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 “…

There is a distinction between "surely" and "almost surely":

http://en.wikipedia.org/wiki/Almost_surely

Bogosort almost surely terminates.

Re: "The worst algorithm in the world?"

#26

Post by eru »

mwbiz wrote: post #11

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.

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

Re: "The worst algorithm in the world?"

#27

Post by vog »

robinhouston wrote: post #21
perlgeek wrote: post #9

> 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 “…

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

Re: "The worst algorithm in the world?"

#28

Post by robinhouston »

kenjackson wrote: post #24
robinhouston wrote: post #20

Earlier quoted context omitted.

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

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

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

Re: "The worst algorithm in the world?"

#29

Post by vog »

kenjackson wrote: post #24
robinhouston wrote: post #20

Earlier quoted context omitted.

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

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

Note that you can optimize this by removing the "(1-c)^n" part, because its absolute value is smaller than 0.5 for big n, so it can't influence the (rounded) result.

This trick is especially funny when performed using a hand calculator. For instance, just calculate the powers of the golden ratio and observe numbers like "xxxxx,0000yyy" "xxxxx,9999yyy", which become closer and closer to integers.

Re: "The worst algorithm in the world?"

#30

Post by akronim »

kenjackson wrote: post #24
robinhouston wrote: post #20

Earlier quoted context omitted.

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

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

can't wait to break this out next time it comes up in an interview!
Post reply on HN