ruby-changes:29780
From: akr <ko1@a...>
Date: Mon, 8 Jul 2013 22:06:11 +0900 (JST)
Subject: [ruby-changes:29780] akr:r41832 (trunk): * bignum.c (rb_big_sq_fast): New function for testing.
akr 2013-07-08 22:05:57 +0900 (Mon, 08 Jul 2013) New Revision: 41832 http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=rev&revision=41832 Log: * bignum.c (rb_big_sq_fast): New function for testing. (rb_big_mul_toom3): Ditto. * internal.h (rb_big_sq_fast): Declared. (rb_big_mul_toom3): Ditto. Modified files: trunk/ChangeLog trunk/bignum.c trunk/ext/-test-/bignum/mul.c trunk/internal.h trunk/test/-ext-/bignum/test_mul.rb Index: ChangeLog =================================================================== --- ChangeLog (revision 41831) +++ ChangeLog (revision 41832) @@ -1,3 +1,11 @@ https://github.com/ruby/ruby/blob/trunk/ChangeLog#L1 +Mon Jul 8 22:03:30 2013 Tanaka Akira <akr@f...> + + * bignum.c (rb_big_sq_fast): New function for testing. + (rb_big_mul_toom3): Ditto. + + * internal.h (rb_big_sq_fast): Declared. + (rb_big_mul_toom3): Ditto. + Mon Jul 8 21:59:34 2013 Tanaka Akira <akr@f...> * bignum.c (bary_mul_balance): Initialize a local variable to suppress Index: ext/-test-/bignum/mul.c =================================================================== --- ext/-test-/bignum/mul.c (revision 41831) +++ ext/-test-/bignum/mul.c (revision 41832) @@ -19,6 +19,12 @@ mul_normal(VALUE x, VALUE y) https://github.com/ruby/ruby/blob/trunk/ext/-test-/bignum/mul.c#L19 } static VALUE +sq_fast(VALUE x) +{ + return rb_big_norm(rb_big_sq_fast(big(x))); +} + +static VALUE mul_balance(VALUE x, VALUE y) { return rb_big_norm(rb_big_mul_balance(big(x), big(y))); @@ -30,12 +36,20 @@ mul_karatsuba(VALUE x, VALUE y) https://github.com/ruby/ruby/blob/trunk/ext/-test-/bignum/mul.c#L36 return rb_big_norm(rb_big_mul_karatsuba(big(x), big(y))); } +static VALUE +mul_toom3(VALUE x, VALUE y) +{ + return rb_big_norm(rb_big_mul_toom3(big(x), big(y))); +} + void Init_mul(VALUE klass) { rb_define_const(rb_cBignum, "SIZEOF_BDIGITS", INT2NUM(SIZEOF_BDIGITS)); rb_define_const(rb_cBignum, "BITSPERDIG", INT2NUM(SIZEOF_BDIGITS * CHAR_BIT)); rb_define_method(rb_cInteger, "big_mul_normal", mul_normal, 1); + rb_define_method(rb_cInteger, "big_sq_fast", sq_fast, 0); rb_define_method(rb_cInteger, "big_mul_balance", mul_balance, 1); rb_define_method(rb_cInteger, "big_mul_karatsuba", mul_karatsuba, 1); + rb_define_method(rb_cInteger, "big_mul_toom3", mul_toom3, 1); } Index: internal.h =================================================================== --- internal.h (revision 41831) +++ internal.h (revision 41832) @@ -518,6 +518,8 @@ VALUE rb_integer_unpack(const void *word https://github.com/ruby/ruby/blob/trunk/internal.h#L518 VALUE rb_big_mul_normal(VALUE x, VALUE y); VALUE rb_big_mul_balance(VALUE x, VALUE y); VALUE rb_big_mul_karatsuba(VALUE x, VALUE y); +VALUE rb_big_mul_toom3(VALUE x, VALUE y); +VALUE rb_big_sq_fast(VALUE x); /* io.c */ void rb_maygvl_fd_fix_cloexec(int fd); Index: bignum.c =================================================================== --- bignum.c (revision 41831) +++ bignum.c (revision 41832) @@ -1515,7 +1515,8 @@ bary_sq_fast(BDIGIT *zds, size_t zn, BDI https://github.com/ruby/ruby/blob/trunk/bignum.c#L1515 MEMZERO(zds, BDIGIT, zn); for (i = 0; i < xn; i++) { v = (BDIGIT_DBL)xds[i]; - if (!v) continue; + if (!v) + continue; c = (BDIGIT_DBL)zds[i + i] + v * v; zds[i + i] = BIGLO(c); c = BIGDN(c); @@ -1525,18 +1526,30 @@ bary_sq_fast(BDIGIT *zds, size_t zn, BDI https://github.com/ruby/ruby/blob/trunk/bignum.c#L1526 c += (BDIGIT_DBL)zds[i + j] + BIGLO(v) * w; zds[i + j] = BIGLO(c); c = BIGDN(c); - if (BIGDN(v)) c += w; + if (BIGDN(v)) + c += w; } if (c) { c += (BDIGIT_DBL)zds[i + xn]; zds[i + xn] = BIGLO(c); c = BIGDN(c); assert(c == 0 || i != xn-1); - if (c && i != xn-1) zds[i + xn + 1] += (BDIGIT)c; + if (c && i != xn-1) + zds[i + xn + 1] += (BDIGIT)c; } } } +VALUE +rb_big_sq_fast(VALUE x) +{ + size_t xn = RBIGNUM_LEN(x), zn = 2 * xn; + VALUE z = bignew(zn, 1); + bary_sq_fast(BDIGITS(z), zn, BDIGITS(x), xn); + RB_GC_GUARD(x); + return z; +} + /* balancing multiplication by slicing larger argument */ static void bary_mul_balance(BDIGIT *zds, size_t zl, BDIGIT *xds, size_t xl, BDIGIT *yds, size_t yl) @@ -4626,6 +4639,12 @@ bigmul1_toom3(VALUE x, VALUE y) https://github.com/ruby/ruby/blob/trunk/bignum.c#L4639 return bignorm(z); } +VALUE +rb_big_mul_toom3(VALUE x, VALUE y) +{ + return bigmul1_toom3(x, y); +} + static VALUE bigmul0(VALUE x, VALUE y) { Index: test/-ext-/bignum/test_mul.rb =================================================================== --- test/-ext-/bignum/test_mul.rb (revision 41831) +++ test/-ext-/bignum/test_mul.rb (revision 41832) @@ -36,6 +36,22 @@ class TestBignum < Test::Unit::TestCase https://github.com/ruby/ruby/blob/trunk/test/-ext-/bignum/test_mul.rb#L36 assert_equal(z, x.big_mul_normal(y)) end + def test_sq_fast + x = (1 << BITSPERDIG) | 1 + z = (1 << 2*BITSPERDIG) | (2 << BITSPERDIG) | 1 + assert_equal(z, x.big_sq_fast) + end + + def test_sq_fast_max2 + x = (BDIGMAX << BITSPERDIG) | BDIGMAX + assert_equal(x.big_mul_normal(x), x.big_sq_fast) + end + + def test_sq_fast_zero_in_middle + x = (BDIGMAX << 2*BITSPERDIG) | BDIGMAX + assert_equal(x.big_mul_normal(x), x.big_sq_fast) + end + def test_mul_balance x = (1 << BITSPERDIG) | 1 y = (1 << BITSPERDIG) | 1 @@ -104,5 +120,11 @@ class TestBignum < Test::Unit::TestCase https://github.com/ruby/ruby/blob/trunk/test/-ext-/bignum/test_mul.rb#L120 assert_equal(x.big_mul_normal(y), x.big_mul_karatsuba(y)) end + def test_mul_toom3 + x = (1 << 2*BITSPERDIG) | (1 << BITSPERDIG) | 1 + y = (1 << 2*BITSPERDIG) | (1 << BITSPERDIG) | 1 + assert_equal(x.big_mul_normal(y), x.big_mul_toom3(y)) + end + end end -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/