Haskell 整数；这里到底发生了什么？

Question

最近对 Haskell 感到好奇，我开始阅读一些东西。 Integer让我大吃一惊。

当我们说 Integer 可以任意大时，这是否意味着我认为的意思（即 Integer 的大小不受 OS)?

假设我有足够的可用 RAM 来容纳具有十亿位值的数字。 Haskell 可以使用那个号码吗？

任何人都可以向我描述一下幕后发生的事情使这成为可能吗？

Answer 1

Haskell 的 Integer 类型通俗地称为 bignum 类型。它的工作方式与您手动执行数学计算的方式大致相同：通过处理数字而不是固定精度的二进制字。

Bignum 库通常将数字存储为 数字集合。 算术的工作方式与您手动执行的方式相同；通过操纵数字。

Answer 2

Say I had enough RAM available to hold a number with a billion place values. Would Haskell be able to work with that number?

Prelude> length . show $ 10^1000000000
1000000001

当然，它确实占用了大量内存

但是你仔细想想——一个字节实际上最多可以存储256>100的数字，即你可以在每个字节中存储两个以上的十进制数字。因此，一个十亿位数的数字应该少于 500 MB 来存储......好吧，显然这里有一些开销需要乘法（同样当我 show 我正在生成一个低效的列表字符串时) 但没什么戏剧性的。

顺便说一句，进行这些计算的不是 Haskell/GHC，而是 GHC 使用的 GMP。

但是您可以自己轻松地在Haskell中实现这样的类型。例如。为简单起见，使用您建议的十进制数字列表^†

newtype DecDigit = DD { getDecDig :: Int }

instance Num [DecDigit] where
  fromInteger n | n < 10     = [DD $ fromInteger n]
                | otherwise  = let (cs,ls) = n`divMod`10
                               in DD $ fromInteger ls : fromInteger cs
  n + [] = n
  [] + n = n
  (DD n₀ : n) + (DD m₀ : m)
     | s₀<10      = DD s₀ : n+m
     | otherwise  = DD (s₀-10) : n+m+[DD 1]
   where s₀ = n₀+m₀

  ...

乘法有点难，但基本上，正如 Robert Harvey 所说，这就像您用笔和纸计算一样。

^†_{这样效率很低！实际实现将不使用十进制数字，而是充分利用机器大小的字（可能使用现代处理器的 128 位甚至 256 位原始操作）。}

Haskell 整数；这里到底发生了什么？

Haskell Integers; What exactly is going on here?

haskell

biginteger