我尝试了Rosettacode的一些例子并遇到了提供的Ackermann示例的问题:当运行它"未修改"时(我用latin-1替换了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
删除第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函数替换了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;
请先阅读JJ的答案.这是轻松的,并导致这个答案实际上是一个详细的解释.
TL; DR A(4,3)是一个非常大的数字,在这个宇宙中无法计算.但是Rakudo会尝试.因为如果你不使用缓存版本和与数值计算相关的限制,你将会超过与内存分配和索引相关的合理限制.
我尝试了Rosettacode的一些例子,并遇到了提供的Ackermann示例的问题
引用任务描述的重点是:
任意精度是首选(因为函数增长如此之快)
P6的标准整数类型Int是任意精度.P6解决方案使用它们来计算可能的最高级答案.它只会在你试图做不可能的事情时失败.
运行时"未修改"(我用latin-1替换了utf-8变量名)
替换变量名称不是一个重大变化.
但添加该A(4,3)行将代码从现实中的可计算性转移到实际上不可计算的.
您修改的示例只有一个解释性注释:
这是一个缓存版本...... 使A(4,2)成为可能
请注意,A(4,2)解决方案的长度接近20,000位.
如果你看一下该页面上的其他解决方案,大多数人甚至都试图达不到A(4,2).在Phix版本上有这样的评论:
优化.仍然没有bignum库,所以ack(4,2),即功率(2,65536)-3,显然是19729位数,以及任何以上,超出(CPU/FPU硬件)和此[代码].
解决方案A(4,2)是最先进的.
A(4,3) 在实践中是不可计算的引用学术孩子:阿克曼功能:
即使对于小输入(比方说为4,3),Ackermann函数的值变得如此之大以至于无法进行可行的计算,实际上它们的十进制展开甚至不能存储在整个物理世界中.
所以计算A(4,3).say是不可能的(在这个宇宙中).
它必然会导致甚至任意精度整数运算的溢出.这只是时间和方式的问题.
Cannot unbox 65536 bit wide bigint into native integer第一条错误消息提到了这行代码:
proto A(Int \m, Int \n) { (state @)[m][n] //= {*} }
这state @是一个匿名状态数组变量.
默认情况下,@变量使用P6的抽象数组类型的默认具体类型.此默认数组类型在实现复杂性和良好性能之间提供了平衡.
虽然计算A(4,2)索引(m和n)仍然足够小,计算完成时不会溢出默认数组的索引限制.
此限制是一个"原生"整数(注意:不是一个"自然"的整数)."本机"整数是P6调用其运行的硬件支持的固定宽度整数,通常是长整数,通常是64位.
64位宽的索引可以处理最多9,223,372,036,854,775,807的索引.
但在尝试计算A(4,3)算法时会生成65536位(8192字节)宽的整数索引.这样的整数可以大到2 65536,一个20,032十进制数字.但允许的最大索引是64位原生整数.因此,除非您注释掉使用数组的缓存行,否则A(4,3)程序最终会抛出异常:
无法将65536位宽的bigint解包为本机整数
正如已经解释过的那样,没有足够大的数组可以帮助完全计算A(4,3).另外,64位整数已经是一个非常大的索引(9,223,372,036,854,775,807).也就是说,P6可以容纳更大的阵列,所以我将在下面简要讨论,因为理论上的可能性可能会引起其他问题的兴趣.
但在讨论运行下面代码的较大数组之前,在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拒绝内存分配请求的结果.
我认为"无法分配...元素"错误是由于超出一些内部Rakudo实现限制而引发的P6级别异常.
最后一条错误消息显示默认数组类型的索引限制,即使程序可用大量内存也是如此.
可以创建/使用支持稀疏数组等内容的其他@(does Positional)数据类型.
并且,使用这种机制,有人可能会编写一个数组实现,支持比默认数组类型支持更大的整数索引(可能是通过在底层平台的指令之上分层逻辑).
如果创建并调用BigArray了这样的替代方案,则可以将缓存行替换为:
my @array is BigArray;
proto A(Int \, Int \) { @array[][] //= {*} }
同样,这仍然不足以存储完全计算的中间结果,A(4,3)但我的观点是显示使用自定义数组类型.
Numeric overflow当您注释掉缓存时,您会得到:
数字溢出
P6/Rakudo做任意精度算术.虽然这有时被称为无限精度是不(不能是)实际上无限的而是替代,那么,"任意",这在计算实际上意味着"健全"为"理智的"的一些定义.
这通常意味着内存不足以存储数字.但是在Rakudo的情况下,我认为在完全耗尽RAM之前,有一种尝试通过从真正的大型切换Int到Num(浮点数)来保持理智.但是,计算A(4,3)最终会溢出甚至双浮.
因此,虽然缓存会更快地爆发,但代码必然会在以后爆炸,然后你会得到一个数字溢出,它会表现为内存不足错误或数字溢出错误,就像在这种情况下一样.
数组下标使用本机int ; 当你使用big int作为数组下标时,这就是你在第3行得到错误的原因.您可能必须定义一个使用Ints作为数组下标的新BigArray.
第二个问题出现在**运算符中:结果是Real,当低级操作返回Num时,它会抛出异常. https://github.com/rakudo/rakudo/blob/master/src/core/Int.pm6#L391-L401
因此,创建BigArray可能无济于事.你也必须创建自己的**,它总是适用于Int,但你似乎已达到无限精度Ints的(不那么无限)限制.