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/