diff options
author | Jeremy Evans <code@jeremyevans.net> | 2021-06-17 11:27:53 -0700 |
---|---|---|
committer | Jeremy Evans <code@jeremyevans.net> | 2021-07-29 15:19:12 -0700 |
commit | 9931e2f5091e95dd947de3b3a00167ae2fd5194a (patch) | |
tree | f8b70b54c37bc3ee0b03b3a057c0bcbfd9f89a5a /numeric.c | |
parent | 64ac984129a7a4645efe5ac57c168ef880b479b2 (diff) |
Improve performance of Integer#digits
This speeds up performance by multiple orders of magnitude for
large integers.
Fixes [Bug #14391]
Co-authored-by: tompng (tomoya ishida) <tomoyapenguin@gmail.com>
Notes
Notes:
Merged: https://github.com/ruby/ruby/pull/4584
Diffstat (limited to 'numeric.c')
-rw-r--r-- | numeric.c | 33 |
1 files changed, 27 insertions, 6 deletions
@@ -4805,7 +4805,7 @@ rb_fix_digits(VALUE fix, long base) static VALUE rb_int_digits_bigbase(VALUE num, VALUE base) { - VALUE digits; + VALUE digits, bases; assert(!rb_num_negative_p(num)); @@ -4823,11 +4823,32 @@ rb_int_digits_bigbase(VALUE num, VALUE base) if (FIXNUM_P(num)) return rb_ary_new_from_args(1, num); - digits = rb_ary_new(); - while (!FIXNUM_P(num) || FIX2LONG(num) > 0) { - VALUE qr = rb_int_divmod(num, base); - rb_ary_push(digits, RARRAY_AREF(qr, 1)); - num = RARRAY_AREF(qr, 0); + if (int_lt(rb_int_div(rb_int_bit_length(num), rb_int_bit_length(base)), INT2FIX(50))) { + digits = rb_ary_new(); + while (!FIXNUM_P(num) || FIX2LONG(num) > 0) { + VALUE qr = rb_int_divmod(num, base); + rb_ary_push(digits, RARRAY_AREF(qr, 1)); + num = RARRAY_AREF(qr, 0); + } + return digits; + } + + bases = rb_ary_new(); + for (VALUE b = base; int_lt(b, num) == Qtrue; b = rb_int_mul(b, b)) { + rb_ary_push(bases, b); + } + digits = rb_ary_new_from_args(1, num); + while (RARRAY_LEN(bases)) { + VALUE b = rb_ary_pop(bases); + long i, last_idx = RARRAY_LEN(digits) - 1; + for(i = last_idx; i >= 0; i--) { + VALUE n = RARRAY_AREF(digits, i); + VALUE divmod = rb_int_divmod(n, b); + VALUE div = RARRAY_AREF(divmod, 0); + VALUE mod = RARRAY_AREF(divmod, 1); + if (i != last_idx || div != INT2FIX(0)) rb_ary_store(digits, 2 * i + 1, div); + rb_ary_store(digits, 2 * i, mod); + } } return digits; |