Bug #14391 » digits_performance.patch
| numeric.c | ||
|---|---|---|
|
static VALUE
|
||
|
rb_int_digits_bigbase(VALUE num, VALUE base)
|
||
|
{
|
||
|
VALUE digits;
|
||
|
VALUE digits, bases;
|
||
|
assert(!rb_num_negative_p(num));
|
||
| ... | ... | |
|
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;
|
||
|
}
|
||
| test/ruby/test_integer.rb | ||
|---|---|---|
|
assert_equal([0, 9, 8, 7, 6, 5, 4, 3, 2, 1], 1234567890.digits)
|
||
|
assert_equal([90, 78, 56, 34, 12], 1234567890.digits(100))
|
||
|
assert_equal([10, 5, 6, 8, 0, 10, 8, 6, 1], 1234567890.digits(13))
|
||
|
assert_equal((2 ** 1024).to_s(7).chars.map(&:to_i).reverse, (2 ** 1024).digits(7))
|
||
|
assert_equal([0] * 100 + [1], (2 ** (128 * 100)).digits(2 ** 128))
|
||
|
end
|
||
|
def test_digits_for_negative_numbers
|
||