CODEWITHSUNDEEP
mathhaskell
zyangpointer
zyangpointer

Reputation: 87

What is the upper bound of Integer in Haskell?

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?

Upvotes: 2

Views: 2388

Answers (1)

Daniel Fischer
Daniel Fischer

Reputation: 183878

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.

Upvotes: 15

Related Questions