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

导致段错误有两个问题：

1 - 函数rb_big_*有时不返回Bignum对象，但当您调用时，第一个 arg必须是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 :(
}

2 -rb_big_pow当您使用两个 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;
}

我不知道所有这些转换对性能的影响。也许，您应该测试它何时是 aFixnum或 aBignum并使用适当的函数或对这两种方法进行基准测试来计算它。

当我运行它时，我想到了一个无限循环，但我不知道我是否用正确的值调用它。

于 2013-11-06T03:14:00.170 回答