Why does this code overflow with Int -> Int?

Question

I am using recursive calls to calc an exponent. It works to 2**63 and then zeros out. I assume I have some overflow. But I thought Haskell handled this.

I tried numbers until 64 and checked into Int.

power :: Int -> Int
power n = if n==0 then 1 else 2*power(n-1)
main = return()

In GHCI

1152921504606846976
*Main> power 70
0
*Main> power 65
0
*Main> power 64
0
*Main> power 63
-9223372036854775808
*Main> power 62
4611686018427387904

Answer 1

I assume I have some overflow. But I thought Haskell handled this.

It is indeed overflow, and Haskell has a type to handle integral numbers with arbitrary size: the Integer. You however use an Int. As the documentation specifies, for an Int:

data Int

A fixed-precision integer type with at least the range [-2^29 .. 2^29-1]. The exact range for a given implementation can be determined by using minBound and maxBound from the Bounded class.

An Int thus has a fixed word size, and can overflow. You can use an Integer however that can represent an arbitrary number (well until the memory is exhausted).

If we thus change the definition to:

power :: Integer -> Integer
power 0 = 1
power n = 2 * power (n-1)

we indeed can calculate 2¹²⁸:

Prelude> power 128
340282366920938463463374607431768211456

Note that we can boost the performance of this power function with:

power :: Integral i => i -> Integer
power 0 = 1
power n | even n = b2 * b2
        | otherwise = 2 * b2 * b2
    where b2 = power (div n 2)

This holds since b^{2 a} = (b^2)a. If we thus assume that all the operations are in constant time, then this algorithm runs in O(log p). This however does not completely hold, since b2 can be quite large, and thus multiplying b2 does not run in constant time.