Project

General

Profile

Feature #12508

Integer#mod_pow

Added by metanest (Makoto Kishimoto) almost 2 years ago. Updated 6 months ago.

Status:
Closed
Priority:
Normal
Target version:
-
[ruby-core:76084]

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() )

(see https://github.com/ruby/ruby/pull/1320 )


Related issues

Has duplicate Ruby trunk - Feature #11003: Fast modular exponentiationClosed

Associated revisions

Revision 9b09cc8a
Added by mrkn (Kenta Murata) 6 months ago

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

Revision 61003
Added by mrkn (Kenta Murata) 6 months ago

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).

Revision 61003
Added by mrkn (Kenta Murata) 6 months ago

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).

Revision 956cfb97
Added by nobu (Nobuyoshi Nakada) 6 months ago

numeric.c: rb_int_powm rdoc

  • numeric.c (Init_Numeric): let rdoc know that rb_int_powm is defined in bignum.c. [Feature #12508] [Feature #11003]

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@61057 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

Revision 61057
Added by nobu (Nobuyoshi Nakada) 6 months ago

numeric.c: rb_int_powm rdoc

  • numeric.c (Init_Numeric): let rdoc know that rb_int_powm is defined in bignum.c. [Feature #12508] [Feature #11003]

Revision 61057
Added by nobu (Nobuyoshi Nakada) 6 months ago

numeric.c: rb_int_powm rdoc

  • numeric.c (Init_Numeric): let rdoc know that rb_int_powm is defined in bignum.c. [Feature #12508] [Feature #11003]

History

#1 [ruby-core:76783] Updated by matz (Yukihiro Matsumoto) almost 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.

#2 [ruby-core:78914] Updated by metanest (Makoto Kishimoto) over 1 year ago

Updated as Integer#pow, with such API.

#3 [ruby-core:79215] Updated by ko1 (Koichi Sasada) over 1 year ago

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

#4 [ruby-core:79665] Updated by matz (Yukihiro Matsumoto) over 1 year ago

Go ahead and add pow(a,b).

Matz.

#5 Updated by mrkn (Kenta Murata) 6 months ago

#6 Updated by mrkn (Kenta Murata) 6 months 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).

Also available in: Atom PDF