Am Donnerstag, 27. Januar 2005 06:08 schrieb William Lee Irwin III:
Inspired by a discussion on freenode #haskell, I tried to write the fastest Fibonacci number function possible, i.e. given a natural number input n to compute F_n. For the moment, mlton-generated binaries crash computing fib (10^8-1), and there is a 6:1 speed difference for fib (10^7-1) between the two, where mlton-generated binaries take just under 1 minute, and ghc- generated binaries take just under 6 minutes.
On Thu, Jan 27, 2005 at 03:26:39PM +0100, Daniel Fischer wrote:
Obviously, your machine is significantly faster than mine. On mine, fib (10^6) takes a little under two minutes, fib (10^7-1) I ^C-ed
~/tmp/fib $(( 10**6 - 1 )) 211.91s user 1.13s system 83% cpu 4:14.96 total In general the printed results and data structures are expected to be in a range where asymptotic behavior dominates. 10^5-1 seems to be the break-even point where more advanced algorithms in Haskell start overtaking naive implementations in lighter-weight runtime systems. This doesn't help much when usefully-advanced languages have sufficiently lightweight runtime systems. I'd almost expect the overhead of printing the result to dominate all this, but somehow it doesn't appear to be the deciding factor, perhaps because they all call gmp to do it. In the range where asymptotic behavior is expected to dominate, the numbers are huge data structures, and having more of them simultaneously live or using more arbitrary-precision temporaries is painful. On Thu, Jan 27, 2005 at 03:26:39PM +0100, Daniel Fischer wrote:
after twenty. I think ,more readable than unfoldl f x = case f x of Nothing -> [] divs 0 = Nothing divs k = Just (uncurry (flip (,)) (k `divMod` 2)) would be unfoldl f x = case f x of Nothing -> [] divs 0 = Nothing divs k = Just (n `quotRem` 2) -- this has no influence on performance, since it's optimized anyway.
unfoldl was intended to match unfoldr's calling convention verbatim, but produce a list in the reverse order, not really to be easy-to-use in this specific problem. Am Donnerstag, 27. Januar 2005 06:08 schrieb William Lee Irwin III:
Anyway, thoughts on how to improve all this from the programmer's point of view, or otherwise explaining what's going on or ameliorating whatever effect is at work here would be appreciated.
On Thu, Jan 27, 2005 at 03:26:39PM +0100, Daniel Fischer wrote:
I thought, I'd do it in the ring of integers in Q(sqrt(5)), code attached, this was a whiff faster for n = 700000 on my machine, a whiff slower for n = 10^6 -- any idea how that may come?
I suspect the divide-and-conquer scheme for exponentiation doesn't do bitreversal, which eliminates various redundant computations. -- wli