Perl6: 无法将65536位宽的大整数转换为本机整数。

Question

我尝试了Rosettacode上的一些示例，并在提供的Ackermann示例中遇到了问题：当“未修改”运行时（我用拉丁字母替换了utf-8变量名），我得到了以下结果（类似但现在可以复制）：

$ 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

在第三行中注释掉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函数的代码中替换了 为 m，替换了 为 n，以更好地进行终端交互以防止复制错误，并尝试注释掉proto声明。我还向Liz提出了问题;)

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;

- Sno

Answer 1

请先阅读JJ的答案。它简洁明了，也导致了这个答案，实际上是对其进行了详细阐述。

TL;DR A(4,3)是一个非常大的数字，在这个宇宙中无法计算。但是raku(do)会尝试计算。如果使用缓存版本，将超过与内存分配和索引相关的合理限制，如果不使用，则会超过与数字计算相关的限制。

---

我尝试了Rosettacode上的一些示例，并在提供的Ackermann示例中遇到了问题。

引用任务说明并添加了一些强调：

任意精度是首选（因为函数增长得非常快）

raku的标准整数类型Int具有任意精度。raku解决方案使用它们来计算可能的最先进答案。只有当您让它尝试做不可能的事情时，它才会失败。

当“未修改”运行它时（我用拉丁-1替换了utf-8变量名）

替换变量名不是重大改变。

但是添加A(4,3)行将代码从可计算现实转变为不可计算现实。

你修改的示例只有一个解释性注释：

这是一个缓存版本...使A(4,2)成为可能 请注意，A(4,2)的解法近20000位数字长度。

如果您查看该页面上的其他解决方案，大多数都没有尝试达到A(4,2)。有像Phix版本上这个评论一样的评论：

优化。仍然没有bignum库，因此ack(4,2)(即power(2,65536)-3)，即19729位数字，以及任何更高位数的数字，都超出了（CPU/FPU硬件）和这个[代码]的范围。 A(4,2)的解决方案是最先进的解决方案。

A(4,3)在实践中无法计算

引用Academic Kids：Ackermann函数：

即使对于小的输入（例如4、3），阿克曼函数的值也变得非常大，无法实际计算，事实上，它们的小数部分甚至无法存储在整个物理宇宙中。因此，在这个宇宙中计算A(4,3)是不可能的。

它必然会导致任意精度整数算术的溢出。这只是时间和方式的问题。

第一个错误消息提到了这行代码：

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

state @ 是一个匿名状态数组变量。

默认情况下，@ 变量使用默认具体类型作为raku的抽象数组类型。这个默认的数组类型提供了实现复杂性和良好性能之间的平衡。

在计算 A(4,2) 时，索引（m 和 n）保持足够小，以便计算完成而不会溢出默认数组的索引限制。

这个限制是一个“本地”整数（注意：不是“自然”整数）。“本地”整数是 raku 所称的硬件支持的固定宽度整数，通常是long long，其大小通常为64位。

一个 64 位宽的索引可以处理高达 9,223,372,036,854,775,807 的索引。

但是，当尝试计算 A(4,3) 时，该算法会生成一个 65536 位（8192 字节）宽的整数索引。这样的整数最大可以达到 2⁶⁵⁵³⁶，是一个20032位十进制数字。但允许的最大索引只能是 64 位本机整数。因此，除非您注释掉使用数组的缓存行，否则对于 A(4,3)，程序最终会抛出异常：

无法将 65536 位宽的大整数拆箱成本机整数

默认数组类型的分配和索引的限制

如前所述，没有任何一个数组可以足够大以完全计算A(4,3)。此外，64位整数已经是相当大的索引（9,223,372,036,854,775,807）。

话虽如此，Raku可以容纳其他数组实现，例如Array::Sparse，因此我将简要讨论这一点，因为这种可能性可能对其他问题也很有趣。

但在讨论更大的数组之前，在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恐慌的结果。这是由于tio.run拒绝了内存分配请求。

我认为"无法分配...元素"错误是一种raku级别的异常，当超过某些内部Rakudo实现限制时会抛出。

最后一个错误消息显示了默认数组类型的索引限制，即使为程序提供了大量内存。

如果有人想要进行更大的索引怎么办？

可以创建/使用其他支持稀疏数组等内容的@（does Positional）数据类型。

通过使用这种机制，可能有人可以编写一个数组实现，它支持比默认数组类型支持的更大的整数索引（可能通过在底层平台指令之上分层逻辑来实现；也许我上面链接的Array::Sparse就是这样做的）。

如果这样的替代方案被称为BigArray，则缓存行可以被替换为：

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

再次强调，这仍然不足以存储完全计算 A(4,3) 的中间结果，但我的观点是展示使用自定义数组类型的用法。

数值溢出

当您注释掉缓存时，会出现以下情况：

数值溢出

Raku/Rakudo 进行任意精度算术。虽然有时称为无限精度，但显然它并不是真正的无限，而是“任意”的，在这种情况下还意味着某些定义下的“理智”。

传统上，这意味着运行内存不足以存储数字。但在 Rakudo 的情况下，我认为有一种尝试通过在完全耗尽 RAM 之前从真正巨大的 Int 切换到 Num（浮点数）来保持事物的理性。但是，最终即使是双精度浮点数也会计算 A(4,3) 而导致溢出。

因此，虽然缓存会更早地崩溃，但代码最终也必定崩溃，然后您将得到一个数值溢出，它可能会表现为内存不足错误或像本例中的数值溢出错误。

- raiph

---

感谢您的详细解释。Jjmerelo给出的答案已经足够让我理解了，但是您深入挖掘并提供了很多合理的思考来更好地了解Rakudo。 - Sno

谢谢反馈，希望您喜欢探索/使用P6/Rakudo。 - raiph

我等待了一段时间才有机会。现在我必须使用CPU时间和内存以不同的方式模拟压力。P6/Rakudo非常有帮助。但Ackermann函数太快死了 ;) - Sno

但是 Ackermann 函数的执行速度太快了。以下是几个想法...1 找到或实现一个算法，它与 大O记号速查表 中的算法和数据结构相匹配。2 访问freenode IRC聊天频道 MoarVM，点击这里 然后按START按钮，输入.ask timotimo Have you got any suggestions for P6 code that would stress cpu and memory in interesting ways? 或类似的内容。 - raiph

谢谢你的提议 - 目前我有一些算法可以胜任这项工作 ;) 有些是纯CPU，有些是内存和CPU，还有些是I/O和CPU。Perl6社区提供的示例非常丰富。我只是想知道为什么Ackermann以我难以理解的方式死亡 - 为了学习P6并不犯同样的错误... - Sno

Answer 2

数组下标使用原生整数; 这就是为什么当你将大整数用作数组下标时，会在第三行出现错误的原因。您可能需要定义一个新的BigArray，它使用Ints作为数组下标。

第二个问题出现在**运算符中：结果是Real，并且当底层操作返回Num时，它会抛出异常。 https://github.com/rakudo/rakudo/blob/master/src/core/Int.pm6#L391-L401

因此，创建BigArray可能并不有用。您将不得不创建自己的**，始终使用Int进行计算，但似乎您已经达到了无限精度Int的（不那么无限）限制。

- jjmerelo