functional-programming - SML 斐波那契大数

Question

我尝试编写自己的 fib 函数，该函数适用于大量（超过 50），但我没有运气。首先，我尝试了明显的解决方案，但很快就溢出了。我的下一个解决方案是这个

    $fun fib(a:int, b:int, index:int) = if(index = 1) then
    $                                      (a+b)
    $                                   else
    $                                       fib(b, (a+b), index - 1);

不幸的是，这也溢出了。

Answer 1

您需要查看IntInf模块，它提供了对任意精度整数的访问。

您可以从 转换Int.int为IntInf.intusing IntInf.fromInt。

请注意，对于您对它们执行的任何操作，您必须使用IntInf.<operation>而不是Int对应的。这包括加法之类的东西。

Answer 2

请注意，在 Poly/ML 中，结构 Int 和 IntInf 默认提供无界（大）整数。由于实现在底部使用了 GNU MP 库，并且在仍然可能的范围内使用小机器整数，所以它也非常快。