Feature #12508
Integer#mod_pow
Description
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() )
Related issues
Associated revisions
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).
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).
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).
History
Updated by matz (Yukihiro Matsumoto) over 2 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.
Matz.
Updated by metanest (Makoto Kishimoto) about 2 years ago
Updated as Integer#pow, with such API.
Updated by ko1 (Koichi Sasada) about 2 years ago
- Assignee set to matz (Yukihiro Matsumoto)
- Status changed from Feedback to Assigned
Updated by matz (Yukihiro Matsumoto) about 2 years ago
Go ahead and add pow(a,b)
.
Matz.
Updated by mrkn (Kenta Murata) about 1 year ago
- Has duplicate Feature #11003: Fast modular exponentiation added
Updated by mrkn (Kenta Murata) about 1 year 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).
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).
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@61003 b2dd03c8-39d4-4d8f-98ff-823fe69b080e