What is the upper bound of Integer in Haskell?
haskell, math
Solution
In Haskell, `Integer` is a - theoretically - unbounded integer type. Fixed-width types are `Int`, `Int8`, `Int16`, `Int32`, `Int64` and the corresponding unsigned `Word`, `Word8` etc.
In practice, even `Integer` is of course bounded, by the available memory for instance, or by the internal representation.
By default, GHC uses the GMP package to represent `Integer`, and that means the bound is `2^(2^37)` or so, since GMP uses a 32-bit integer to store the number of limbs.
Problem
I was solving a math problem: want to get the sum of the digits of the number `2^1000`. In Java, the solution is like: ``` String temp = BigInteger.ONE.shiftLeft(1000).toString(); int sum = 0; for (int i = 0; i < temp.length(); i++) sum += temp.charAt(i) - '0'; ``` Then came up a solution in Haskell, like this: ``` digitSum ::(Integral a) => a -> a digitSum 0 = 0 digitSum n = (mod n 10) + (digitSum (div n 10)) ``` The whole process is pretty smooth, one point seems interesting, we know integer type can not handle `2 ^ 1000`, too big, in Java, it's obvious to use `BigInteger` and treat the big number to string, but in Haskell, no compiling errors means the `2 ^ 1000` could be passed in directly. Here is the thing, does Haskell transform the number into string internally? I want to make sure what the type is and let the compiler to determine, then I type the following lines in GHCi: ``` Prelude> let i = 2 ^ 1000 Prelude> i 107150860718626732094842504906000181056140481170553360744375038837035105112493612249319 837881569585812759467291755314682518714528569231404359845775746985748039345677748242309 854210746050623711418779541821530464749835819412673987675591655439460770629145711964776 86542167660429831652624386837205668069376 Prelude> :t i i :: Integer ``` Here, I was totally confused, apparently, the number of `i` is oversized, but the return type of `i` is still `Integer`. How could we explain this and what's the upper bound or limit of `Integer` of Haskell?