[Haskell-cafe] Efficiency question
Bertram Felgenhauer
bertram.felgenhauer at googlemail.com
Wed May 30 09:35:36 EDT 2007
Evil Bro wrote:
>
> > Counting can be done elegantly by 'filter' and 'length':
> I figured out the following code after posting:
>
> solve d = length [(y,x) | x <- [2..d], y <- [1..(x-1)], gcd x y == 1]
> main = print (solve 1000000)
>
> However when running it, it gave an answer of -1255316543. How on earth can
> a length be negative?
Yu got an integer overflow - length returns an Int. You can use
Data.List.genericLength instead, however, which can return its
result in any Num instance. (In particular, Integer works)
> import Data.List
>
> solve :: Integer -> Integer
> solve d = genericLength [(y,x) | x <- [2..d], y <- [1..(x-1)], gcd x y == 1]
>
> main = print (solve 1000000)
(Note: untested.)
HTH,
Bertram
More information about the Haskell-Cafe
mailing list