biginteger - perl6 : Cannot unbox 65536 bit wide bigint into native integer

Question

我尝试了一些来自 Rosettacode 的例子并遇到提供的 Ackermann 示例的问题:当“未修改”运行它时(我将 utf-8 变量名替换为 latin-1 变量名)，我得到(类似，但现在可复制):

$ perl6 t/ackermann.p6
65533
19729 digits starting with 20035299304068464649790723515602557504478254755697...
Cannot unbox 65536 bit wide bigint into native integer
  in sub A at t/ackermann.p6 line 3
  in sub A at t/ackermann.p6 line 11
  in sub A at t/ackermann.p6 line 3
  in block <unit> at t/ackermann.p6 line 17

删除第 3 行中的 proto 声明(通过注释掉):

$ perl6 t/ackermann.p6
65533
19729 digits starting with 20035299304068464649790723515602557504478254755697...
Numeric overflow
  in sub A at t/ackermann.p6 line 8
  in sub A at t/ackermann.p6 line 11
  in block <unit> at t/ackermann.p6 line 17

什么地方出了错？该程序不会分配太多内存。自然整数是有限的吗？

我替换了来自 Ackermann function 的代码带有 m 的 𝑚 和带有 n 的 𝑛 用于更好的终端交互以复制错误并尝试注释掉 proto 声明。我也问过莉兹 ;)

use v6;

proto A(Int \m, Int \n) { (state @)[m][n] //= {*} }

multi A(0,      Int \n) { n + 1 }
multi A(1,      Int \n) { n + 2 }
multi A(2,      Int \n) { 3 + 2 * n }
multi A(3,      Int \n) { 5 + 8 * (2 ** n - 1) }

multi A(Int \m, 0     ) { A(m - 1, 1) }
multi A(Int \m, Int \n) { A(m - 1, A(m, n - 1)) }

# Testing:
say A(4,1);
say .chars, " digits starting with ", .substr(0,50), "..." given A(4,2);

A(4, 3).say;

Answer 1

请先阅读JJ的回答。它很轻松，并导致了这个答案，这实际上是对它的详细阐述。
TL;博士 A(4,3)是一个非常大的数字，在这个宇宙中无法计算。但是 raku(do) 会尝试的。如果您使用缓存版本，那么您将超过与内存分配和索引相关的合理限制，如果不使用与数字计算相关的限制。

I try some examples from Rosettacode and encounter an issue with the provided Ackermann example

用一些 引用任务描述强调 :

Arbitrary precision is preferred (since the function grows so quickly)

raku 的标准整数类型 Int是 arbitrary precision . raku 解决方案使用它们来计算可能的最高级答案。只有当你让它尝试做不可能的事情时，它才会失败。

When running it "unmodified" (I replaced the utf-8 variable names by latin-1 ones)

替换变量名并不是一个重大的变化。
但是添加 A(4,3) Line 将代码从现实中的可计算转变为现实中的不可计算。
您修改的示例只有一个解释性注释:

Here's a caching version of that ... to make A(4,2) possible

请注意 A(4,2)解决方案的长度接近 20,000 位。
如果您查看该页面上的其他解决方案，请不要尝试访问 A(4,2) . Phix版本有这样的评论:

optimised. still no bignum library, so ack(4,2), which is power(2,65536)-3, which is apparently 19729 digits, and any above, are beyond (the CPU/FPU hardware) and this [code].

A(4,2) 的解决方案是最先进的。 A(4,3)在实践中是不可计算的
报价 Academic Kids: Ackermann function :

Even for small inputs (4,3, say) the values of the Ackermann function become so large that they cannot be feasibly computed, and in fact their decimal expansions cannot even be stored in the entire physical universe.

所以计算 A(4,3).say是不可能的(在这个宇宙中)。
它必然会导致甚至任意精度整数运算的溢出。这只是时间和方式的问题。 Cannot unbox 65536 bit wide bigint into native integer第一条错误消息提到了这行代码:

proto A(Int \m, Int \n) { (state @)[m][n] //= {*} }

state @是 anonymous state array variable .
默认 @变量使用 the default concrete type乐的 abstract array type .这种默认数组类型在实现复杂性和不错的性能之间提供了平衡。
计算时 A(4,2)索引( m 和 n )保持足够小，以便计算完成而不会溢出默认数组的索引限制。
此限制是“ native ”整数(注意:不是 "natural" integer )。 “ native ”整数是 raku 所说的由它运行的硬件支持的固定宽度整数，通常是 long long这通常是 64 位。
一个 64 位宽的索引可以处理最大 9,223,372,036,854,775,807 的索引.
但是在尝试计算 A(4,3)该算法生成一个 65536 位(8192 字节)宽的整数索引。这样的整数可能与 265536、 20,032 decimal digit number 一样大.但允许的最大索引是 64 位 native 整数。因此，除非您注释掉使用数组的缓存行，否则对于 A(4,3)程序最终抛出异常:

Cannot unbox 65536 bit wide bigint into native integer

默认数组类型的分配和索引限制
正如已经解释过的，没有任何数组可以大到足以帮助完全计算 A(4,3) .此外，一个 64 位整数已经是一个相当大的索引( 9,223,372,036,854,775,807 )。
也就是说，raku 可以容纳其他数组实现，例如 Array::Sparse 所以我将在下面简要讨论，因为其他问题可能会对这些可能性感兴趣。
但在讨论更大的数组之前， running the code below on tio.run显示该平台上默认数组类型的实际限制:

my @array;
@array[2**29]++; # works
@array[2**30]++; # could not allocate 8589967360 bytes
@array[2**60]++; # Unable to allocate ... 1152921504606846977 elements
@array[2**63]++; # Cannot unbox 64 bit wide bigint into native integer

(注释掉错误行以查看以后/更大的错误。)
“无法分配 8589967360 字节”错误是 MoarVM panic 。这是 tio.run 拒绝内存分配请求的结果。
我认为“无法分配...元素”错误是由于超出某些内部 Rakudo 实现限制而引发的 raku 级别异常。
最后一条错误消息显示了默认数组类型的索引限制，即使大量内存可供程序使用。
如果有人想做更大的索引怎么办？
可以创建/使用其他 @ ( does Positional ) 支持稀疏数组等内容的数据类型。
而且，使用这种机制，有人可能会编写一个数组实现，该实现支持比默认数组类型支持的更大的整数索引(大概是通过在底层平台指令之上的分层逻辑；也许我上面链接的 Array::Sparse 确实如此) )。
如果这样的替代方案被称为 BigArray那么缓存行可以替换为:

my @array is BigArray;
proto A(Int \𝑚, Int \𝑛) { @array[𝑚][𝑛] //= {*} }

同样，这仍然不足以存储完全计算的中期结果 A(4,3)但我的观点是展示自定义数组类型的使用。 Numeric overflow当您注释掉缓存时，您会得到:

Numeric overflow

Raku/Rakudo 做任意精度算术。虽然这有时被称为无限精度，但它显然实际上并不是无限的，而是“任意的”，在这种情况下，对于“理智”的某些定义，这也意味着“理智”。
这通常意味着内存不足，无法存储数字。但在 Rakudo 的情况下，我认为这是通过从真正庞大的 Int 切换来保持理智的一种尝试。到 Num (一个浮点数)在完全耗尽 RAM 之前。但随后计算 A(4,3)最终甚至会溢出双浮点数。
因此，虽然缓存会更快地爆炸，但无论如何代码肯定会在以后爆炸，然后你会得到一个数字溢出，它要么表现为内存不足错误，要么表现为数字溢出错误，就像在这种情况下一样。