3

Ruby ネイティブ C メソッドである power mod に取り組んでいます。これが私が得たものです：

#define TO_BIGNUM(x) (FIXNUM_P(x) ? rb_int2big(FIX2LONG(x)) : x)
#define CONST2BIGNUM(x) (TO_BIGNUM(INT2NUM(x)))

VALUE method_big_power_mod(VALUE self, VALUE base, VALUE exp, VALUE mod){
  VALUE res = TO_BIGNUM(INT2NUM(1));

  base = TO_BIGNUM(base);
  exp = TO_BIGNUM(exp);
  mod = TO_BIGNUM(mod);

  while (rb_big_cmp(exp, CONST2BIGNUM(0))) {
    if (rb_big_modulo(exp, CONST2BIGNUM(2))) {
      VALUE mul = rb_big_mul(res, base);
      res = rb_big_modulo(mul, mod);
    }
    base = rb_big_modulo(rb_big_pow(base, CONST2BIGNUM(2)), mod);
    exp = rb_big_div(exp, CONST2BIGNUM(2));
  }

  return res;
}

毎回セグメンテーション違反になります。問題をrb_big_modulo通話に切り分けました。gdb stacktrace は、bigdivremを呼び出した後にメソッドでクラッシュすると言っていrb_big_moduloます。のソースを調べてみましたbignum.cが、クラッシュの原因がわかりません。私は何か間違ったことをしていますか？

4

1 に答える 1

1

segfault の原因となっている 2 つの問題があります。

1 - 関数はオブジェクトをrb_big_*返さないことがありBignumますが、呼び出すときは最初の引数がオブジェクトでなければなりませんBignum。例えば：

if (rb_big_modulo(exp, CONST2BIGNUM(2))) {
  VALUE mul = rb_big_mul(res, base); // This maybe return a Fixnum 
  res = rb_big_modulo(mul, mod); // This will cause a segfault :(
}

rb_big_pow2 -両方の args で関数を呼び出すとBignum、警告がFloat表示され、オブジェクトに簡単に変換できないオブジェクトが返されBignumます。したがって、それを呼び出す行を次のように置き換える必要があります。

VALUE x = TO_BIGNUM(rb_big_pow(base, INT2NUM(2))); // Power by a Fixnum instead a Bignum
base = TO_BIGNUM(rb_big_modulo(x , mod));

最終的な実装は次のようになります。

#define TO_BIGNUM(x) (FIXNUM_P(x) ? rb_int2big(FIX2LONG(x)) : x)
#define CONST2BIGNUM(x) (TO_BIGNUM(INT2NUM(x)))

VALUE method_big_power_mod(VALUE self, VALUE base, VALUE exp, VALUE mod){
  VALUE res = TO_BIGNUM(INT2NUM(1));

  base = TO_BIGNUM(base);
  exp = TO_BIGNUM(exp);
  mod = TO_BIGNUM(mod);

  while (rb_big_cmp(exp, CONST2BIGNUM(0))) {
    if (rb_big_modulo(exp, CONST2BIGNUM(2))) {
      VALUE mul = TO_BIGNUM(rb_big_mul(res, base));
      res = TO_BIGNUM(rb_big_modulo(mul, mod));
    }
    VALUE x = TO_BIGNUM(rb_big_pow(base, INT2NUM(2)));

    base = TO_BIGNUM(rb_big_modulo(x , mod));
    exp = TO_BIGNUM(rb_big_div(exp, CONST2BIGNUM(2)));
  }

  return res;
}

これらすべての変換によるパフォーマンスへの影響はわかりません。Fixnumおそらく、それが aまたは aの場合をテストBignumし、適切な関数を使用して計算するか、両方のアプローチをベンチマークする必要があります。

実行すると無限ループに陥りましたが、正しい値で呼び出すかどうかはわかりません。

于 2013-11-06T03:14:00.170 に答える