how to make it faster ?
Hi, I wrote a type program to compute fibonacci series, if the max value is big, then it becomes very slow. like take 100 fib How can I make it faster :-)
>>>>>>>>>> fibo 0 = 0 fibo 1 = 1 fibo (n+2) = (fibo n) + (fibo (n+1)) fib :: [Int] fib = [fibo i | i <- [0..]]
On 24 March 2010 16:01, 国平张
Hi,
I wrote a type program to compute fibonacci series, if the max value is big, then it becomes very slow. like
take 100 fib
How can I make it faster :-)
Use a better algorithm: http://tinyurl.com/ya3vvye Try doing your code by hand for say "fibo 5" to see why it's so bad (hint: GHC does not do CSE in general). -- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com IvanMiljenovic.wordpress.com
On Mar 24, 2010, at 6:01 PM, 国平张 wrote:
Hi,
I wrote a type program to compute fibonacci series,
It certainly is possible to compute Fibonacci numbers as a "type program", but what you wrote is not a type program, just plain old Haskell.
if the max value is big, then it becomes very slow. like
take 100 fib
How can I make it faster :-)
Don't do it that way. Each element of your list is computed independently, and each computation takes exponential time (and would in C or Java). There are well known ways to compute Fibonacci numbers in linear and logarithmic time (assuming integer operations are constant time, which of course isn't true for big enough integers). They work well in Haskell too. The simplest thing -in Haskell- is to make the list element computations share the work using lazy evaluation. fibs :: [Integer] fibs = 1 : 1 : [x+y | (x,y) <- zip fibs (tail fibs)]
participants (3)
-
Ivan Miljenovic -
Richard O'Keefe -
国平张