1

以下 D 程序会因输入 939971 或更高版本而崩溃，但不会因输入 939970 或更低版本而崩溃：

#!/usr/bin/rdmd --shebang -w -d-debug --relocation-model=pic
    import std.stdio;
import std.bigint;
import std.conv;
import std.array;
//extern (C) void fibonacci (int* pointer, int length);
int main(string[] args)
{
  args.popFront();
  foreach(size_t i, string a; args) {
    writeln(fibonacci(to!BigInt(a)));
  }
  return 0;
}



BigInt fibonacci (BigInt input)
{
  struct FibMatrix
  {
    BigInt a;
    BigInt b;
    BigInt d;

    this(bool test)
    {
      a = 1;
      if (test) {
        b = 1; d = 0;
      } else {
        b = 0; d = 1;
      }
    }

    void square()
    {
      BigInt f = b^^2;
      b = b*(a + d);
      a = a^^2 + f;
      d = d^^2 + f;
    }

    void opOpAssign(string op, FibMatrix) (FibMatrix input)
    {
      static if (op == "*")
      {
        BigInt temp1 = b * input.b;
        d *= input.d;
        d += temp1;
        b *= input.d;
        b += a*input.b;
        a *= input.a;
        a += temp1;
      } else static assert(0, "Unsupported operator");
    }
  }
  if (input == 0) {
    return BigInt(0);
  } else {
    input -= 1;
  }
  FibMatrix base = FibMatrix(true);
  FibMatrix result = FibMatrix(false);
  version (none)
  {
    writeln (result.a);
    writeln (result.b);
    writeln (result.d);
  }
  if (input % 2 == 1) {
    result *= base;
  }
  version (none)
  {
    writeln (result.a);
    writeln (result.b);
    writeln (result.d);
  }
  input /= 2;
  while (input > 0) {
    base.square();
    if (input % 2 == 1) {
      result *= base;
    }
    input /= 2;
  }
  return result.a;
}

堆栈跟踪：

#0  0x0000003c51b492e6 in __memcpy_ssse3_back () from /lib64/libc.so.6
#1  0x000000000043d6d8 in std.internal.math.biguintcore.inplaceSub() ()
#2  0x000000000043c340 in std.internal.math.biguintcore.mulKaratsuba() ()
#3  0x000000000043c519 in std.internal.math.biguintcore.mulKaratsuba() ()
#4  0x000000000043ad34 in std.internal.math.biguintcore.mulInternal() ()
#5  0x000000000043a7ef in std.internal.math.biguintcore.BigUint.mul() ()
#6  0x000000000040a8a6 in std.bigint.BigInt.__T10opOpAssignVAyaa1_2aTS3std6bigint6BigIntZ.opOpAssign() ()
#7  0x0000000000403f00 in std.bigint.BigInt.__T8opBinaryVAyaa1_2aTS3std6bigint6BigIntZ.opBinary() ()
#8  0x000000000040456b in getints.fibonacci() ()
#9  0x00000000004035d9 in getints.fibonacci() ()
#10 0x0000000000402f4a in D main ()
#11 0x000000000045bfea in rt.dmain2._d_run_main() ()
#12 0x000000000045bc06 in _d_run_main ()
#13 0x0000003c51a21b45 in __libc_start_main () from /lib64/libc.so.6
#14 0x0000000000402d29 in _start ()

对我来说，这看起来像是 Phobos 中的一个错误——我说得对吗？

4

2 回答 2

1

我认为您的应用程序进程已达到堆栈大小限制。当我编译和运行时，我得到的是：

object.Error: Access Violation
----------------
0x0041DDDC
----------------
Press any key to continue . . .

0x0041DDDC 是一个熟悉的数字——它正好是 4MB (4 * 1024 * 1024)。所以我的第一个猜测是 - 你达到了堆栈大小限制。

更新：一点点挖掘 DMD 设置的默认堆栈大小导致在D 论坛上找到此线程。根据该线程，DMD 显然设置了 4k 千字节 (4mb) 堆栈大小，我相信这可以解释为什么我们会收到上述错误。

于 2013-11-24T11:12:23.640 回答
1

问题是 std.BigInt 中的一个错误，它在乘以过大的 BigInt 值时会导致崩溃。这可能是因为 Karatsuba 乘法算法的实现不好，因为阻止它被使用可以解决问题，迫使它使用标准的 BigInts 乘法方式（这对于如此大的输入效率较低，但没有错误）。

于 2013-12-28T15:38:59.333 回答