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
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 IntA 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 usingminBoundandmaxBoundfrom theBoundedclass.
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 2128:
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 b2 a = (b2)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.
p in your answer? You mean b2 again, right?
Integertype for arbitrary sized integers, theIntis however a fixed word size integer.