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

31–40 of 73 posts

Re: "The worst algorithm in the world?"

#31

Post by stralep »

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.

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"

Re: "The worst algorithm in the world?"

#32

Post by kenjackson »

robinhouston wrote: post #28
kenjackson wrote: post #24

Earlier quoted context omitted.

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

When you round you'll always get the exact integer answer, even using the precision of the golden ratio I gave in the code.

Re: "The worst algorithm in the world?"

#33

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.

> The closed form complexity is not the same (not sure how it could be)

I disagree. Both variants are more similar than it may seem at a first glance. In essence, the question here is which of the following calculations is more efficient for big n:

a) the power function for arbitrary precision floating point

b) the power function for 2x2 matrices of arbitrary precision integers

Assuming that we can ignore the initial effort to calculate the golden ratio (can we?), Binet's formula is based on a), while the article's best algorith is an application of b).

I'm absolutely undecided which one works better, mostly because both kinds of power functions are working essentially the same way, with a complexity of O(log(n)).

Also, the precisions required for both cases seem to be quite similar.

Re: "The worst algorithm in the world?"

#34

Post by kenjackson »

vog wrote: post #33
kenjackson wrote: post #24

Earlier quoted context omitted.

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

> The closed form complexity is not the same (not sure how it could be) I disagree. Both variants are more similar than it may seem at a first glance. In essence, the question here is which of the following calculations is more efficient for big n: a) the power function for arbitrary precision floating point b) the power function for 2x2 matrices of arbitrary precision integers Assuming that we can ignore the initial…

Indeed. I thought the OP was referring to the recursive algorithm, not the final algorithm.

Re: "The worst algorithm in the world?"

#35

Post by robinhouston »

kenjackson wrote: post #32
robinhouston wrote: post #28

Earlier quoted context omitted.

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.

When you round you'll always get the exact integer answer, even using the precision of the golden ratio I gave in the code.

That’s really not true. You don’t have to take my word for it: try it with fib(1000), say.

The answer should be:

  43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

Re: "The worst algorithm in the world?"

#36

Post by vog »

stralep wrote: post #31
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.

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"

This is a great method! It avoids arbitrary floating point arithmetics[1] and thus makes it more comparable with the method presented in the article.

As far as I can see, this algorithm is very similar to the matrix operations of the article, at least in terms of complexity.

[1] Only the very last step might involve fp arithmetics, because you'll have to convert the result pair (x,y) back to x+y*sqrt(5). However, we already know that the result has to be an integer, so the its second part will always be 0, no fp arithmetics required.

Re: "The worst algorithm in the world?"

#37

Post by sevenproxies »

mccutchen wrote: post #2

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.

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.

Re: "The worst algorithm in the world?"

#38

Post by ot »

stralep wrote: post #31
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.

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"

> Z ring enriched (if this is right word) with sqrt(5)

I think "extended" is the right word (see http://en.wikipedia.org/wiki/Ring_extension)

It is commonly denoted as Z[sqrt(5)]

Re: "The worst algorithm in the world?"

#39

Post by TheBoff »

ubasu wrote: post #8

It seems the author hasn't read SICP: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html...

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.

Post reply on HN