ruby-changes:42491
From: akr <ko1@a...>
Date: Wed, 13 Apr 2016 21:55:17 +0900 (JST)
Subject: [ruby-changes:42491] akr:r54565 (trunk): * array.c (rb_ary_sum): Array#sum is implemented.
akr 2016-04-13 22:51:53 +0900 (Wed, 13 Apr 2016) New Revision: 54565 https://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=revision&revision=54565 Log: * array.c (rb_ary_sum): Array#sum is implemented. Kahan's compensated summation algorithm for precise sum of float numbers is moved from ary_inject_op in enum.c. * enum.c (ary_inject_op): Don't specialize for float numbers. [ruby-core:74569] [Feature#12217] proposed by mrkn. Modified files: trunk/ChangeLog trunk/array.c trunk/enum.c trunk/test/ruby/test_array.rb trunk/test/ruby/test_enum.rb Index: enum.c =================================================================== --- enum.c (revision 54564) +++ enum.c (revision 54565) @@ -634,7 +634,6 @@ ary_inject_op(VALUE ary, VALUE init, VAL https://github.com/ruby/ruby/blob/trunk/enum.c#L634 ID id; VALUE v, e; long i, n; - double f, c; if (RARRAY_LEN(ary) == 0) return init == Qundef ? Qnil : init; @@ -656,7 +655,7 @@ ary_inject_op(VALUE ary, VALUE init, VAL https://github.com/ruby/ruby/blob/trunk/enum.c#L655 rb_method_basic_definition_p(rb_cFixnum, idPLUS) && rb_method_basic_definition_p(rb_cBignum, idPLUS)) { n = 0; - while (1) { + for (; i < RARRAY_LEN(ary); i++) { e = RARRAY_AREF(ary, i); if (FIXNUM_P(e)) { n += FIX2LONG(e); /* should not overflow long type */ @@ -668,49 +667,18 @@ ary_inject_op(VALUE ary, VALUE init, VAL https://github.com/ruby/ruby/blob/trunk/enum.c#L667 else if (RB_TYPE_P(e, T_BIGNUM)) v = rb_big_plus(e, v); else - break; - i++; - if (RARRAY_LEN(ary) <= i) - return n == 0 ? v : rb_fix_plus(LONG2FIX(n), v); + goto not_integer; } - if (n != 0) { + if (n != 0) v = rb_fix_plus(LONG2FIX(n), v); - } - if (RB_FLOAT_TYPE_P(e) && - rb_method_basic_definition_p(rb_cFloat, idPLUS)) { - f = NUM2DBL(v); - goto sum_float; - } - } - else if (RB_FLOAT_TYPE_P(v) && - rb_method_basic_definition_p(rb_cFloat, idPLUS)) { - f = RFLOAT_VALUE(v); - sum_float: - c = 0.0; - while (1) { - double x, y, t; - e = RARRAY_AREF(ary, i); - if (RB_FLOAT_TYPE_P(e)) - x = RFLOAT_VALUE(e); - else if (FIXNUM_P(e)) - x = FIX2LONG(e); - else if (RB_TYPE_P(e, T_BIGNUM)) - x = rb_big2dbl(e); - else - break; - - y = x - c; - t = f + y; - c = (t - f) - y; - f = t; + return v; - i++; - if (RARRAY_LEN(ary) <= i) - return DBL2NUM(f); - } + not_integer: + if (n != 0) + v = rb_fix_plus(LONG2FIX(n), v); } } - for (; i<RARRAY_LEN(ary); i++) { + for (; i < RARRAY_LEN(ary); i++) { v = rb_funcall(v, id, 1, RARRAY_AREF(ary, i)); } return v; Index: array.c =================================================================== --- array.c (revision 54564) +++ array.c (revision 54565) @@ -5651,6 +5651,92 @@ rb_ary_dig(int argc, VALUE *argv, VALUE https://github.com/ruby/ruby/blob/trunk/array.c#L5651 } /* + * call-seq: + * ary.sum -> number + * + * Returns the sum of elements. + * For example, [e1, e2, e3].sum returns 0 + e1 + e2 + e3. + * + * If <i>ary</i> is empty, it returns 0. + * + * [].sum #=> 0 + * [1, 2, 3].sum #=> 6 + * [3, 5.5].sum #=> 8.5 + * + * This method may not respect method redefinition of "+" methods + * such as Fixnum#+. + * + */ + +VALUE +rb_ary_sum(VALUE ary) +{ + VALUE v, e; + long i, n; + + if (RARRAY_LEN(ary) == 0) + return LONG2FIX(0); + + v = LONG2FIX(0); + + n = 0; + for (i = 0; i < RARRAY_LEN(ary); i++) { + e = RARRAY_AREF(ary, i); + if (FIXNUM_P(e)) { + n += FIX2LONG(e); /* should not overflow long type */ + if (!FIXABLE(n)) { + v = rb_big_plus(LONG2NUM(n), v); + n = 0; + } + } + else if (RB_TYPE_P(e, T_BIGNUM)) + v = rb_big_plus(e, v); + else + goto not_integer; + } + if (n != 0) + v = rb_fix_plus(LONG2FIX(n), v); + return v; + + not_integer: + if (n != 0) + v = rb_fix_plus(LONG2FIX(n), v); + + if (RB_FLOAT_TYPE_P(e)) { + /* Kahan's compensated summation algorithm */ + double f, c; + f = NUM2DBL(v); + c = 0.0; + for (; i < RARRAY_LEN(ary); i++) { + double x, y, t; + e = RARRAY_AREF(ary, i); + if (RB_FLOAT_TYPE_P(e)) + x = RFLOAT_VALUE(e); + else if (FIXNUM_P(e)) + x = FIX2LONG(e); + else if (RB_TYPE_P(e, T_BIGNUM)) + x = rb_big2dbl(e); + else + goto not_float; + + y = x - c; + t = f + y; + c = (t - f) - y; + f = t; + } + return DBL2NUM(f); + + not_float: + v = DBL2NUM(f); + } + + for (; i < RARRAY_LEN(ary); i++) { + v = rb_funcall(v, idPLUS, 1, RARRAY_AREF(ary, i)); + } + return v; +} + +/* * Arrays are ordered, integer-indexed collections of any object. * * Array indexing starts at 0, as in C or Java. A negative index is assumed @@ -6005,6 +6091,7 @@ Init_Array(void) https://github.com/ruby/ruby/blob/trunk/array.c#L6091 rb_define_method(rb_cArray, "bsearch_index", rb_ary_bsearch_index, 0); rb_define_method(rb_cArray, "any?", rb_ary_any_p, 0); rb_define_method(rb_cArray, "dig", rb_ary_dig, -1); + rb_define_method(rb_cArray, "sum", rb_ary_sum, 0); id_cmp = rb_intern("<=>"); id_random = rb_intern("random"); Index: test/ruby/test_enum.rb =================================================================== --- test/ruby/test_enum.rb (revision 54564) +++ test/ruby/test_enum.rb (revision 54565) @@ -217,13 +217,6 @@ class TestEnumerable < Test::Unit::TestC https://github.com/ruby/ruby/blob/trunk/test/ruby/test_enum.rb#L217 assert_float_equal(10.0, [3.0, 5].inject(2.0, :+)) assert_float_equal((FIXNUM_MAX+1).to_f, [0.0, FIXNUM_MAX+1].inject(:+)) assert_equal(2.0+3.0i, [2.0, 3.0i].inject(:+)) - - large_number = 100000000 - small_number = 1e-9 - until (large_number + small_number) == large_number - small_number /= 10 - end - assert_equal(large_number+(small_number*10), [large_number, *[small_number]*10].inject(:+)) end def test_inject_array_plus_redefined Index: test/ruby/test_array.rb =================================================================== --- test/ruby/test_array.rb (revision 54564) +++ test/ruby/test_array.rb (revision 54565) @@ -1,6 +1,7 @@ https://github.com/ruby/ruby/blob/trunk/test/ruby/test_array.rb#L1 # coding: US-ASCII # frozen_string_literal: false require 'test/unit' +require "rbconfig/sizeof" class TestArray < Test::Unit::TestCase def setup @@ -2710,6 +2711,39 @@ class TestArray < Test::Unit::TestCase https://github.com/ruby/ruby/blob/trunk/test/ruby/test_array.rb#L2711 assert_raise(TypeError) {h.dig(1, 0)} end + FIXNUM_MIN = -(1 << (8 * RbConfig::SIZEOF['long'] - 2)) + FIXNUM_MAX = (1 << (8 * RbConfig::SIZEOF['long'] - 2)) - 1 + + def assert_float_equal(e, v, msg=nil) + assert_equal(Float, v.class, msg) + assert_equal(e, v, msg) + end + + def test_sum + assert_equal(0, [].sum) + assert_equal(3, [3].sum) + assert_equal(8, [3, 5].sum) + assert_equal(15, [3, 5, 7].sum) + assert_float_equal(15.0, [3, 5, 7.0].sum) + assert_equal(2*FIXNUM_MAX, Array.new(2, FIXNUM_MAX).sum) + assert_equal(2*(FIXNUM_MAX+1), Array.new(2, FIXNUM_MAX+1).sum) + assert_equal(10*FIXNUM_MAX, Array.new(10, FIXNUM_MAX).sum) + assert_equal(0, ([FIXNUM_MAX, 1, -FIXNUM_MAX, -1]*10).sum) + assert_equal(FIXNUM_MAX*10, ([FIXNUM_MAX+1, -1]*10).sum) + assert_equal(2*FIXNUM_MIN, Array.new(2, FIXNUM_MIN).sum) + assert_equal((FIXNUM_MAX+1).to_f, [FIXNUM_MAX, 1, 0.0].sum) + assert_float_equal(8.0, [3.0, 5].sum) + assert_float_equal((FIXNUM_MAX+1).to_f, [0.0, FIXNUM_MAX+1].sum) + assert_equal(2.0+3.0i, [2.0, 3.0i].sum) + + large_number = 100000000 + small_number = 1e-9 + until (large_number + small_number) == large_number + small_number /= 10 + end + assert_equal(large_number+(small_number*10), [large_number, *[small_number]*10].sum) + end + private def need_continuation unless respond_to?(:callcc, true) Index: ChangeLog =================================================================== --- ChangeLog (revision 54564) +++ ChangeLog (revision 54565) @@ -1,3 +1,13 @@ https://github.com/ruby/ruby/blob/trunk/ChangeLog#L1 +Wed Apr 13 22:51:38 2016 Tanaka Akira <akr@f...> + + * array.c (rb_ary_sum): Array#sum is implemented. + Kahan's compensated summation algorithm for precise sum of float + numbers is moved from ary_inject_op in enum.c. + + * enum.c (ary_inject_op): Don't specialize for float numbers. + + [ruby-core:74569] [Feature#12217] proposed by mrkn. + Wed Apr 13 15:56:35 2016 Nobuyoshi Nakada <nobu@r...> * numeric.c (flo_ceil): add an optional parameter, digits, as -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/