[前][次][番号順一覧][スレッド一覧]

ruby-changes:30071

From: akr <ko1@a...>
Date: Tue, 23 Jul 2013 07:16:56 +0900 (JST)
Subject: [ruby-changes:30071] akr:r42123 (trunk): * bignum.c (bary_mulsub_1xN): New function.

akr	2013-07-23 07:16:45 +0900 (Tue, 23 Jul 2013)

  New Revision: 42123

  http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=rev&revision=42123

  Log:
    * bignum.c (bary_mulsub_1xN): New function.
      (bary_mul_toom3): Use bary_mulsub_1xN.

  Modified files:
    trunk/ChangeLog
    trunk/bignum.c

Index: ChangeLog
===================================================================
--- ChangeLog	(revision 42122)
+++ ChangeLog	(revision 42123)
@@ -1,3 +1,8 @@ https://github.com/ruby/ruby/blob/trunk/ChangeLog#L1
+Tue Jul 23 07:14:31 2013  Tanaka Akira  <akr@f...>
+
+	* bignum.c (bary_mulsub_1xN): New function.
+	  (bary_mul_toom3): Use bary_mulsub_1xN.
+
 Tue Jul 23 03:32:23 2013  Tanaka Akira  <akr@f...>
 
 	* bignum.c (KARATSUBA_BALANCED): New macro.
Index: bignum.c
===================================================================
--- bignum.c	(revision 42122)
+++ bignum.c	(revision 42123)
@@ -1571,6 +1571,46 @@ bary_muladd_1xN(BDIGIT *zds, size_t zl, https://github.com/ruby/ruby/blob/trunk/bignum.c#L1571
     return n != 0;
 }
 
+static BDIGIT_DBL_SIGNED
+bigdivrem_mulsub(BDIGIT *zds, size_t zn, BDIGIT x, BDIGIT *yds, size_t yn)
+{
+    size_t i;
+    BDIGIT_DBL t2;
+    BDIGIT_DBL_SIGNED num;
+
+    assert(zn == yn + 1);
+
+    num = 0;
+    t2 = 0;
+    i = 0;
+
+    do {
+        BDIGIT_DBL ee;
+        t2 += (BDIGIT_DBL)yds[i] * x;
+        ee = num - BIGLO(t2);
+        num = (BDIGIT_DBL)zds[i] + ee;
+        if (ee) zds[i] = BIGLO(num);
+        num = BIGDN(num);
+        t2 = BIGDN(t2);
+    } while (++i < yn);
+    num += zds[i] - t2; /* borrow from high digit; don't update */
+    return num;
+}
+
+static int
+bary_mulsub_1xN(BDIGIT *zds, size_t zn, BDIGIT x, BDIGIT *yds, size_t yn)
+{
+    BDIGIT_DBL_SIGNED num;
+
+    assert(zn == yn + 1);
+
+    num = bigdivrem_mulsub(zds, zn, x, yds, yn);
+    zds[yn] = BIGLO(num);
+    if (BIGDN(num))
+        return 1;
+    return 0;
+}
+
 static void
 bary_mul_normal(BDIGIT *zds, size_t zl, BDIGIT *xds, size_t xl, BDIGIT *yds, size_t yl)
 {
@@ -2222,11 +2262,7 @@ bary_mul_toom3(BDIGIT *zds, size_t zn, B https://github.com/ruby/ruby/blob/trunk/bignum.c#L2262
         bary_muladd_1xN(z3ds, z3n, 2, t4ds, t4n);
     }
     else {
-        /* TODO: combining with next addition */
-        t1ds[t4n] = bary_small_lshift(t1ds, t4ds, t4n, 1);
-        t1n = t4n+1;
-        t1p = t4p;
-        if (bary_sub(z3ds, z3n, z3ds, z3n, t1ds, t1n)) {
+        if (bary_mulsub_1xN(z3ds, z3n, 2, t4ds, t4n)) {
             bary_2comp(z3ds, z3n);
             z3p = !z3p;
         }
@@ -5102,32 +5138,6 @@ struct big_div_struct { https://github.com/ruby/ruby/blob/trunk/bignum.c#L5138
     volatile VALUE stop;
 };
 
-static BDIGIT_DBL_SIGNED
-bigdivrem_mulsub(BDIGIT *zds, size_t zn, BDIGIT x, BDIGIT *yds, size_t yn)
-{
-    size_t i;
-    BDIGIT_DBL t2;
-    BDIGIT_DBL_SIGNED num;
-
-    assert(zn == yn + 1);
-
-    num = 0;
-    t2 = 0;
-    i = 0;
-
-    do {
-        BDIGIT_DBL ee;
-        t2 += (BDIGIT_DBL)yds[i] * x;
-        ee = num - BIGLO(t2);
-        num = (BDIGIT_DBL)zds[i] + ee;
-        if (ee) zds[i] = BIGLO(num);
-        num = BIGDN(num);
-        t2 = BIGDN(t2);
-    } while (++i < yn);
-    num += zds[i] - t2; /* borrow from high digit; don't update */
-    return num;
-}
-
 static void *
 bigdivrem1(void *ptr)
 {

--
ML: ruby-changes@q...
Info: http://www.atdot.net/~ko1/quickml/

[前][次][番号順一覧][スレッド一覧]