[Haskell-cafe] how to optmize this code?
Daniel Fischer
daniel.is.fischer at googlemail.com
Wed Mar 30 17:02:23 CEST 2011
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
More information about the Haskell-Cafe
mailing list