diff options
-rw-r--r-- | ChangeLog | 5 | ||||
-rw-r--r-- | bignum.c | 20 | ||||
-rw-r--r-- | test/-ext-/bignum/test_mul.rb | 43 |
3 files changed, 54 insertions, 14 deletions
@@ -1,3 +1,8 @@ +Sun Jul 7 23:56:32 2013 Tanaka Akira <akr@fsij.org> + + * bignum.c (bary_mul_karatsuba): Unreachable code removed. Remove + several branches. + Sun Jul 7 22:59:06 2013 Tanaka Akira <akr@fsij.org> * internal.h (rb_big_mul_normal): Declared. @@ -1593,8 +1593,8 @@ bary_mul_karatsuba(BDIGIT *zds, size_t zl, BDIGIT *xds, size_t xl, BDIGIT *yds, size_t n; int sub_p, borrow, carry1, carry2, carry3; - int odd_x = 0; int odd_y = 0; + int odd_xy = 0; BDIGIT *xds0, *xds1, *yds0, *yds1, *zds0, *zds1, *zds2, *zds3; @@ -1606,7 +1606,7 @@ bary_mul_karatsuba(BDIGIT *zds, size_t zl, BDIGIT *xds, size_t xl, BDIGIT *yds, odd_y = 1; yl--; if (yl < xl) { - odd_x = 1; + odd_xy = 1; xl--; } } @@ -1706,15 +1706,10 @@ bary_mul_karatsuba(BDIGIT *zds, size_t zl, BDIGIT *xds, size_t xl, BDIGIT *yds, if (carry2) bary_add_one(zds2, zl-2*n); - if (borrow && carry1) - borrow = carry1 = 0; - if (borrow && carry3) - borrow = carry3 = 0; - - if (borrow) + if (carry1 + carry3 - borrow < 0) bary_sub_one(zds3, zl-3*n); - else if (carry1 || carry3) { - BDIGIT c = carry1 + carry3; + else if (carry1 + carry3 - borrow > 0) { + BDIGIT c = carry1 + carry3 - borrow; bary_add(zds3, zl-3*n, zds3, zl-3*n, &c, 1); } @@ -1729,13 +1724,10 @@ bary_mul_karatsuba(BDIGIT *zds, size_t zl, BDIGIT *xds, size_t xl, BDIGIT *yds, } */ - if (odd_x && odd_y) { + if (odd_xy) { bary_muladd_1xN(zds+yl, zl-yl, yds[yl], xds, xl); bary_muladd_1xN(zds+xl, zl-xl, xds[xl], yds, yl+1); } - else if (odd_x) { - bary_muladd_1xN(zds+xl, zl-xl, xds[xl], yds, yl); - } else if (odd_y) { bary_muladd_1xN(zds+yl, zl-yl, yds[yl], xds, xl); } diff --git a/test/-ext-/bignum/test_mul.rb b/test/-ext-/bignum/test_mul.rb index ad3b38febd..539b9cf138 100644 --- a/test/-ext-/bignum/test_mul.rb +++ b/test/-ext-/bignum/test_mul.rb @@ -6,6 +6,7 @@ class TestBignum < Test::Unit::TestCase SIZEOF_BDIGITS = Bignum::SIZEOF_BDIGITS BITSPERDIG = Bignum::BITSPERDIG + BDIGMAX = (1 << BITSPERDIG) - 1 def test_mul_normal x = (1 << BITSPERDIG) | 1 @@ -49,5 +50,47 @@ class TestBignum < Test::Unit::TestCase assert_equal(z, x.big_mul_karatsuba(y)) end + def test_mul_karatsuba_odd_y + x = (1 << BITSPERDIG) | 1 + y = (1 << (2*BITSPERDIG)) | 1 + assert_equal(x.big_mul_normal(y), x.big_mul_karatsuba(y)) + end + + def test_mul_karatsuba_odd_xy + x = (1 << (2*BITSPERDIG)) | 1 + y = (1 << (2*BITSPERDIG)) | 1 + assert_equal(x.big_mul_normal(y), x.big_mul_karatsuba(y)) + end + + def test_mul_karatsuba_x1_gt_x0 + x = (2 << BITSPERDIG) | 1 + y = (1 << BITSPERDIG) | 2 + assert_equal(x.big_mul_normal(y), x.big_mul_karatsuba(y)) + end + + def test_mul_karatsuba_y1_gt_y0 + x = (1 << BITSPERDIG) | 2 + y = (2 << BITSPERDIG) | 1 + assert_equal(x.big_mul_normal(y), x.big_mul_karatsuba(y)) + end + + def test_mul_karatsuba_x1_gt_x0_and_y1_gt_y0 + x = (2 << BITSPERDIG) | 1 + y = (2 << BITSPERDIG) | 1 + assert_equal(x.big_mul_normal(y), x.big_mul_karatsuba(y)) + end + + def test_mul_karatsuba_carry2 + x = (1 << BITSPERDIG) | BDIGMAX + y = (1 << BITSPERDIG) | BDIGMAX + assert_equal(x.big_mul_normal(y), x.big_mul_karatsuba(y)) + end + + def test_mul_karatsuba_borrow + x = (BDIGMAX << BITSPERDIG) | 1 + y = (BDIGMAX << BITSPERDIG) | 1 + assert_equal(x.big_mul_normal(y), x.big_mul_karatsuba(y)) + end + end end |