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

71–73 of 73 posts

Re: "The worst algorithm in the world?"

#71

Post by robinhouston »

shasta wrote: post #57
btilly wrote: post #51

Earlier quoted context omitted.

Yes, I have actually done the math. On the surface it looks very different, but a lot of the same numbers show up in intermediate calculations.

Well, both have computed the Fibonacci terms at a given level, so how different could it be? Here's my implementation: def fib_fast2(n): assert n >= 0 a, b = 2, 0 # invariant: a,b are components of 2(phi^n) for bit in bits(n): a, b = (a*a + 5*b*b)>>1, a*b if bit: a, b = (a + 5*b)>>1, (a+b)>>1 return b It's almost identical runtime as the one in the article - a hair slower (15.32s vs. 16.17s to compute fib 10M). They'…

That’s very nice! And a little rearrangement will bring it from three to two “big multiplications”, making it faster than my routine:

  def fib_ring2(n):
    assert n >= 0
    a, b = 2, 0 # invariant: phi^n = (a + b*sqrt(5)) / 2
    for bit in bits(n):
        ab = a*b
        a, b = (a+b)*((a+5*b)//2) - 3*ab, ab
        if bit: a, b = (a + 5*b)//2, (a+b)//2
    return b

Re: "The worst algorithm in the world?"

#72

Post by sesqu »

sevenproxies wrote: post #69
nandemo wrote: post #62

Earlier quoted context omitted.

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

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

Re: "The worst algorithm in the world?"

#73

Post by shasta »

robinhouston wrote: post #71
shasta wrote: post #57

Earlier quoted context omitted.

Well, both have computed the Fibonacci terms at a given level, so how different could it be? Here's my implementation: def fib_fast2(n): assert n >= 0 a, b = 2, 0 # invariant: a,b are components of 2(phi^n) for bit in bits(n): a, b = (a*a + 5*b*b)>>1, a*b if bit: a, b = (a + 5*b)>>1, (a+b)>>1 return b It's almost identical runtime as the one in the article - a hair slower (15.32s vs. 16.17s to compute fib 10M). They'…

That’s very nice! And a little rearrangement will bring it from three to two “big multiplications”, making it faster than my routine: def fib_ring2(n): assert n >= 0 a, b = 2, 0 # invariant: phi^n = (a + b*sqrt(5)) / 2 for bit in bits(n): ab = a*b a, b = (a+b)*((a+5*b)//2) - 3*ab, ab if bit: a, b = (a + 5*b)//2, (a+b)//2 return b

Oops, I should have found that. I looked and thought there was some reason it wouldn't work. Interesting post, thanks for the fun.
Post reply on HN