Segfault в D для слишком больших входов

Следующая программа 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 ()

Похоже, ошибка в Фобосе для меня - я прав?

Источник

2 ответа

Решение

Проблема заключалась в ошибке в std.BigInt, которая вызывала сбой при умножении чрезмерно больших значений BigInt. Это может быть связано с плохой реализацией алгоритма умножения Карацубы, так как предотвращение его использования решает проблему, заставляя его использовать стандартный способ умножения BigInts (который менее эффективен для таких больших входных данных, но не имеет ошибки).

Источник

Я думаю, что ваш процесс приложения достигает предела размера стека. Когда я собираю и запускаю, я получаю вот что:

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

0x0041DDDC - знакомое число - оно точно 4 МБ (4 * 1024 * 1024). Итак, мое первое предположение - вы достигли предела размера стека.

ОБНОВЛЕНИЕ: небольшое копание того, какой размер стека по умолчанию устанавливает DMD, привело к нахождению этой темы на форуме D. Согласно этой теме, DMD устанавливает размер стека в 4 килобайта (4Мб), что, как я полагаю, объясняет, почему мы получили ошибку выше.

Источник
Другие вопросы по тегам