Large numbers become negative in haskell

Question

(product (take 9 [1000,999..])) `div` (product (map (\j-> product [1..j]) (map (\j->length(j)) (group [2,2,2,2,2,2,2,2,2]))))

The above code is of the form X div Y, with X=product (take 9 [1000,999..]) & Y=(product (map (\j-> product [1..j]) (map (\j->length(j)) (group [2,2,2,2,2,2,2,2,2]))))

If I copy and paste the code in ghci, it gives me -12740133310672 as an answer, but if I count X & Y individually, I get 964541486381834014456320000 & 362880, then dividing them gives me 2658017764500203964000 as an answer.

I think this incoherence might be because the number is too large, but since the computer can calculate X and Y correctly individually, how come it can't also divide them combined?

Answer 1

Prelude Data.List> let x = product $ take 9 [1000,999..]

Prelude Data.List> x
964541486381834014456320000
Prelude Data.List> :t x
x :: (Enum a, Num a) => a

Observe that x has the type of a generic number: you calculated it with just operations that work for any number type. When you evaluate such a number in GHCi, it defaults to the “safest” concrete type, which is Integer, an arbitrary-precision type which has no problem with big numbers. However, you can enforce the calculation to be done with any other numerical type:

Prelude Data.List> x :: Integer
964541486381834014456320000
Prelude Data.List> x :: Float
9.645414e26
Prelude Data.List> x :: Double
9.645414863818342e26
Prelude Data.List> x :: Int
-4623139575776374784

The floating point versions are inaccurate but still close, whereas Int (a machine-size fixed precision number) simply overflows and gives complete bogus.

Normally this won't bother you, because huge calculations are by default done with the safe Integer type.

That is, unless something else prevents it.

Prelude Data.List> let y = product (map (\j-> product [1..j]) $ map length (group [2,2,2,2,2,2,2,2,2]))

Prelude Data.List> y
362880
Prelude Data.List> :t y
y :: Int

Unlike x, the type of y is already concrete: it must be Int, because that's the result type of length. (The rationale being: a list that's so big that you couldn't measure its length with an Int would not be able to fit in memory anyway.)

Now, div, like most numeric functions in Haskell, requires that the arguments and result have all the same type. For this reason, x`div`y will as a whole be calculated as Int instead of Integer, including x. And as we've seen, calculating x as Int gives bogus.

OTOH, if you use 362880 as a literal, then this isn't connected to length. It's just a generic number, like x, hence GHCi will again default to safe Integer, i.e. you get

Prelude Data.List> x `div` 362880
2658017764500203964000

The same result can be achieved if you just allow conversion of y:

Prelude Data.List> x `div` fromIntegral y
2658017764500203964000