Project

General

Profile

Bug #14391 » digits_performance.patch

tompng (tomoya ishida), 01/24/2018 12:45 PM

View differences:

numeric.c
4793 4793
static VALUE
4794 4794
rb_int_digits_bigbase(VALUE num, VALUE base)
4795 4795
{
4796
    VALUE digits;
4796
    VALUE digits, bases;
4797 4797

  
4798 4798
    assert(!rb_num_negative_p(num));
4799 4799

  
......
4811 4811
    if (FIXNUM_P(num))
4812 4812
        return rb_ary_new_from_args(1, num);
4813 4813

  
4814
    digits = rb_ary_new();
4815
    while (!FIXNUM_P(num) || FIX2LONG(num) > 0) {
4816
        VALUE qr = rb_int_divmod(num, base);
4817
        rb_ary_push(digits, RARRAY_AREF(qr, 1));
4818
        num = RARRAY_AREF(qr, 0);
4814
    if (int_lt(rb_int_div(rb_int_bit_length(num), rb_int_bit_length(base)), INT2FIX(50))) {
4815
	digits = rb_ary_new();
4816
	while (!FIXNUM_P(num) || FIX2LONG(num) > 0) {
4817
	    VALUE qr = rb_int_divmod(num, base);
4818
	    rb_ary_push(digits, RARRAY_AREF(qr, 1));
4819
	    num = RARRAY_AREF(qr, 0);
4820
	}
4821
	return digits;
4822
    }
4823

  
4824
    bases = rb_ary_new();
4825
    for (VALUE b = base; int_lt(b, num) == Qtrue; b = rb_int_mul(b, b)) {
4826
	rb_ary_push(bases, b);
4827
    }
4828
    digits = rb_ary_new_from_args(1, num);
4829
    while (RARRAY_LEN(bases)) {
4830
	VALUE b = rb_ary_pop(bases);
4831
	long i, last_idx = RARRAY_LEN(digits) - 1;
4832
	for(i = last_idx; i >= 0; i--) {
4833
	    VALUE n = RARRAY_AREF(digits, i);
4834
	    VALUE divmod = rb_int_divmod(n, b);
4835
	    VALUE div = RARRAY_AREF(divmod, 0);
4836
	    VALUE mod = RARRAY_AREF(divmod, 1);
4837
	    if (i != last_idx || div != INT2FIX(0)) rb_ary_store(digits, 2 * i + 1,  div);
4838
	    rb_ary_store(digits, 2 * i, mod);
4839
	}
4819 4840
    }
4820

  
4821 4841
    return digits;
4822 4842
}
4823 4843

  
test/ruby/test_integer.rb
444 444
    assert_equal([0, 9, 8, 7, 6, 5, 4, 3, 2, 1], 1234567890.digits)
445 445
    assert_equal([90, 78, 56, 34, 12], 1234567890.digits(100))
446 446
    assert_equal([10, 5, 6, 8, 0, 10, 8, 6, 1], 1234567890.digits(13))
447
    assert_equal((2 ** 1024).to_s(7).chars.map(&:to_i).reverse, (2 ** 1024).digits(7))
448
    assert_equal([0] * 100 + [1], (2 ** (128 * 100)).digits(2 ** 128))
447 449
  end
448 450

  
449 451
  def test_digits_for_negative_numbers