Feature #11003

Fast modular exponentiation

Added by venkatvb (venkatesh babu) almost 3 years ago. Updated 4 months ago.

Target version:


I would like to suggest, implementing "fast Modular Exponentiation " ( for fixnum class.
Eg: A function like pow(a, n, MOD) can be computed more efficiently than (a**n) % MOD

Related issues

Is duplicate of CommonRuby - Feature #12508: Integer#mod_powClosed

Associated revisions

Revision 61003
Added by mrkn (Kenta Murata) 4 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 61057
Added by nobu (Nobuyoshi Nakada) 3 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]


#1 Updated by mrkn (Kenta Murata) almost 3 years ago

  • Description updated (diff)

#2 Updated by mrkn (Kenta Murata) almost 3 years ago

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

I have two questions:

  • Do you have some concrete use cases in which this new feature is used?
  • Why don't you make a gem library to provide this feature? or Are there gem libraries providing it?

#3 Updated by mrkn (Kenta Murata) 4 months ago

#4 [ruby-core:84022] Updated by mrkn (Kenta Murata) 4 months ago

  • Status changed from Feedback to Closed

The same function was accepted in #12508

Also available in: Atom PDF