Feature #12508



Added by metanest (Makoto Kishimoto) about 8 years ago. Updated over 2 years ago.

Target version:


A new method Integer#mod_pow, power with modulo.

a.mod_pow(b, m) #=> (a**b) % m

Sometimes a**b becomes very large number, then naive
implementation may be unefficient. Fast implementation
is useful.
(with USE_GMP symbol, this implement uses mpz_powm() )

(see )

Related issues 1 (0 open1 closed)

Has duplicate Ruby master - Feature #11003: Fast modular exponentiationClosedmatz (Yukihiro Matsumoto)Actions

Updated by matz (Yukihiro Matsumoto) almost 8 years ago

  • Status changed from Open to Feedback

Instead, I propose pow(a) and pow(a,b) where the latter works as mod_pow() here.


Updated by metanest (Makoto Kishimoto) over 7 years ago

Updated as Integer#pow, with such API.

Updated by ko1 (Koichi Sasada) over 7 years ago

  • Status changed from Feedback to Assigned
  • Assignee set to matz (Yukihiro Matsumoto)

Updated by matz (Yukihiro Matsumoto) over 7 years ago

Go ahead and add pow(a,b).


Actions #5

Updated by mrkn (Kenta Murata) over 6 years ago

Actions #6

Updated by mrkn (Kenta Murata) over 6 years ago

  • Status changed from Assigned to Closed

Applied in changeset ruby-trunk:trunk|r61003.

bignum.c, numeric.c: add Integer#pow(b, m)

This commit is based on the pull-request #1320 created by Makoto Kishimoto.
[Feature #12508] [Feature #11003] [close GH-1320]

  • bignum.c (rb_int_powm): Added for Integer#pow(b, m).

  • internal.h (rb_int_powm): Declared to refer in numeric.c.

  • bignum.c (bary_powm_gmp): Added for Integer#pow(b, m) using GMP.

  • bignum.c (int_pow_tmp1): Added for implementing Integer#pow(b, m).

  • bignum.c (int_pow_tmp2, int_pow_tmp3): ditto.

  • internal.h (rb_num_positive_int_p): Moved from numeric.c for sharing
    the definition with bignum.c.

  • internal.h (rb_num_negative_int_p, rb_num_compare_with_zero): ditto.

  • numeric.c(negative_int_p): Moved to internal.h for sharing the
    definition with bignum.c.

  • numeric.c (positive_int_p, compare_with_zero): ditto.

  • numeric.c (rb_int_odd_p): Exported (renamed from int_odd_p).

  • internal.h (rb_int_odd_p): ditto.

  • internal.h (HALF_LONG_MSB): Added.

  • numeric.c (SQRT_LONG_MAX): Redefined by using HALF_LONG_MSB.

  • test/ruby/test_numeric.rb (test_pow): Added for Integer#pow(b, m).

Actions #7

Updated by hsbt (Hiroshi SHIBATA) over 2 years ago

  • Project changed from 14 to Ruby master

Also available in: Atom PDF