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 ()

私にはフォボスのバグのように見えます - 私は正しいですか?

4

2 に答える 2

1

この問題は std.BigInt のバグであり、過度に大きな BigInt 値を乗算するとクラッシュが発生しました。これはカラツバ乗算アルゴリズムの不適切な実装が原因である可能性があります。これを使用しないようにすると問題が修正され、BigInt を乗算する標準的な方法を使用するように強制されるためです (このような大きな入力に対しては効率が低下しますが、バグはありません)。 ）。

于 2013-12-28T15:38:59.333 に答える