[Haskell-cafe] how to optmize this code?

[Yves Parès]

If I'm not wrong :

sum [1..n] = (n² + n)/2


2011/3/30 Daniel Fischer <daniel.is.fischer at googlemail.com>

> On Wednesday 30 March 2011 16:39:49, Gilberto Garcia wrote:
> > Hi Haskellers,
> >
> > I was solving this problem from project euler to study haskell.
> > I came up whit the following solution and I was wondering if there is
> > a more optimized and concise solution.
>
> Yes. There's a constant-time formula for summing the multiples of k <= a
> (those are [k, 2*k .. (a `quot` k) * k],
> so the sum is k* sum [1 .. (a `quot` k)],
> try to find a formula for sum [1 .. n]), then you need the
> http://en.wikipedia.org/wiki/Inclusion–exclusion_principle
>
> If you're looking for multiples of any of few numbers, it's very simple
> then. For longer lists (say you want to sum the multiples of any of 30
> numbers), you have to be clever implementing the inclusion-exclusion
> algorithm to keep the running time low, sometimes other methods may be
> faster then (fkSum (10^7) [2 .. 30] for example).
>
> >
> > fkSum :: Int -> [Int] -> Int
> > fkSum a [] = 0
> > fkSum a (b) = foldl (+) 0 (filter (\x -> isMultiple x b) [1..a])
> >
> > isMultiple :: Int -> [Int] -> Bool
> > isMultiple a [] = False
> > isMultiple a (x:xs) = if (mod a x == 0) then True else isMultiple a xs
> >
> > Thanks in advance
> > ggarcia
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20110330/56ddd79c/attachment.htm>