1

所以，我一直在学习 C# 并测试一些简单的算法。我制作了这个简单的类，它公开了一个递归斐波那契数函数。我使用记忆（动态编程）来存储以前找到的数字。这是代码：

    using Godot;
    using System.Collections.Generic;

    public class Exercise1 : Node {
      private BigInteger teste = new BigInteger(1);
      private Dictionary<BigInteger,BigInteger> memory = new Dictionary<BigInteger,BigInteger>();
      public override void _Ready() {
        RunBigIntegerCraziness();
      }

    private void RunBigIntegerCraziness() {
      for (int i = 0; i < 31227; i++) {
        GD.Print($"fib number {i} is {fib(new BigInteger(i))}");
      }
    }

    private BigInteger fib(BigInteger n) {
      if (memory.ContainsKey(n)) {
        return memory[n];
      }

      if (n <= 2) {
        memory[n] = 1;
        return 1;
      }

      memory[n - 2] = fib(n - 2);
      memory[n - 1] = fib(n - 1);

      return memory[n - 2] + memory[n - 1];
    }
    }

忽略“戈多”部分。只是我在游戏项目中对此进行了测试。一切都编译得很好，但我只能计算到斐波那契 n。3226. 如果我转到等于 3227 及以上的数字，我会得到这个异常：

[...] fib 编号 3225 是 fib 编号 3226 是6992660514518607877846098955621488368282416352196347538962582793677413201081503778426120021618792727702775372690628582418382475456849167641670980026645237969148458290914186731576570453888991926749608189535570098806870592480072043098043435965998152944229365016726187236595847736509426931947811080302930848764428479051650851764798904663189920298514346825378156627018359028522923033504212912655168388868295581350718393726782389523398564524027820797178217862590684964765041586757629512750783685050750901040341048172688357174809036130726448063421809839706042920247511864953877922562123285460436398946436246517063640730190098135913847164646444408273613505609156948848849137776674366318992029851434682537815662701835902852292303350421291265516838886829558135071839372678238952339856452402782079717821786259068496476504158675762951275078368505075090104034104817268835717480903613072644806342180983970604292024751186495387792256212328546043639894643624651706364073019009813591384716464644440827361350560915694884884913777667436631899202985143468253781566270183590285229230335042129126551683888682955813507183937267823895233985645240278207971782178625906849647650415867576295127507836850507509010403410481726883571748090361307264480634218098397060429202475118649538779225621232854604363989464362465170636407301900981359138471646464444082736135056091569488488491377766743

未处理的异常：System.ArithmeticException：算术运算中的溢出或下溢。在 BigInteger.op_Addition (BigInteger bi1, BigInteger bi2) [0x000fa] in :0 at Exercise1.fib (BigInteger n) [0x000a8] 在 /Users/rafael/gamedev/godot/mytests/CSharpStudy/study_classes/Exercise1.cs:31 at练习1.RunBigIntegerCraziness () [0x00006] 在/Users/rafael/gamedev/godot/mytests/CSharpStudy/study_classes/Exercise1.cs:15 在Exercise1._Ready () [0x00001] 在/Users/rafael/gamedev/godot/mytests/ CSharpStudy/study_classes/Exercise1.cs:10 终端进程以退出代码终止：1

“BigInteger”不是应该处理相当高的数字吗？

4

1 回答 1

4

在那个 BigInteger 的源代码中，有：

// maximum length of the BigInteger in uint (4 bytes)
// change this to suit the required level of precision.
private const int maxLength = 70;

长度以肢体计算，在此实现中每个肢体为 32 位。此外，最上肢的最上位被视为符号位。因此，在不改变源的情况下，这种 BigInteger 可以存储的最大数量（这个限制不适用于 System.Numerics 中的 BigInteger）是 2 70*32-1 -1，或者换句话说，有 2239 “正常”位可用。

这允许一些相当大的整数，但不够大：根据 Wolfram Alpha fib(3227) 需要刚刚超过 2239 位，因此它不适合。

于 2020-02-23T20:36:29.963 回答