haskell - 为什么这段代码会因 Int -> Int 而溢出？

Question

我正在使用递归调用来计算指数。它工作到 2**63，然后归零。我想我有一些溢出。但我认为 Haskell 处理了这个问题。

我尝试了 64 之前的数字并 checkin Int。

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

在 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.

这确实是溢出，Haskell 有一种类型可以处理任意大小的整数: Integer 。但是，您使用 Int 。正如文档所指定的，对于 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.

Int 因此具有固定的字大小，并且可能溢出。您可以使用Integer，但是它可以表示任意数字(直到内存耗尽)。

如果我们将定义更改为:

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

我们确实可以计算2¹²⁸:

Prelude> power 128
340282366920938463463374607431768211456

请注意，我们可以通过以下方式提高此 power 函数的性能:

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

从b^{2 a} = (b^2)a开始，这一点成立。如果我们假设所有操作都在常数时间内完成，那么该算法的运行时间为O(log p)。然而，这并不完全成立，因为 b2 可能非常大，因此乘法 b2 不会在恒定时间内运行。