CODEWITHSUNDEEP
haskellmodulo
user7629669
user7629669

Reputation:

Haskell mod malfunction?

Here is my Haskell function to remove 2::Int and 5::Int from a list:

remPrimesFactors25 :: [Int] -> [Int]
remPrimesFactors25 [] = []
remPrimesFactors25 (x:xs)
  | x == 2                  = remPrimesFactors25 xs
  | x == 5                  = remPrimesFactors25 xs
  | otherwise           = x : remPrimesFactors25 xs

λ>  remPrimesFactors25 [2,5,23]
[23]
λ>  remPrimesFactors25 [2,5,23] == [23]
True
λ>  product (remPrimesFactors25 [2,5,23])
23
λ>  product [23]
23
λ>  product (remPrimesFactors25 [2,5,23]) == product [23]
True

Here's my problem. Why does this happen?

λ>  mod (10^22) (product (remPrimesFactors25 [2,5,23]) )
15
λ>  mod (10^22) (product [23])
1

Upvotes: 2

Views: 102

Answers (2)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476503

You are working with an Int. An Int uses a fixed number of bits, and can represent at least all values in the range of -229 to 229-1. Typically on 32-bit machine it will take the range of -231 to 231-1, and on a 64-bit machine -263 to 263-1. 10^22 however is greater than these ranges. This means that 10^22 for an Int will be represented on a 64-bit machine for example as 1'864'712'049'423'024'128.

If you use an Integer, which can represent values of arbitrary size, then there is no such problem. If you thus rewrite the function to:

remPrimesFactors25 :: [Integer] -> [Integer]
remPrimesFactors25 = filter (\x -> x != 2 && x != 5)

then 10^22 will be interpreted as an Integer, and thus 10^22 will take as value 10'000'000'000'000'000'000'000.

You however do not need to calculate 10^22. You can use algorithms like powerMod :: (Integral a, Integral b) => a -> b -> a -> a of the arithmoi package.

Upvotes: 2

chepner
chepner

Reputation: 530843

remPrimesFactors always returns a list of Int values, not Integer values. Since mod requires both arguments to have the same type, 10^22 is also treated as an Int, which doesn't have the precision to handle the large number accurately.

Prelude> 10^22 :: Integer
10000000000000000000000
Prelude> 10^22 :: Int
1864712049423024128

Upvotes: 2

Related Questions