aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--ChangeLog10
-rw-r--r--bignum.c37
-rw-r--r--ext/-test-/bignum/depend1
-rw-r--r--ext/-test-/bignum/mul.c41
-rw-r--r--internal.h3
-rw-r--r--test/-ext-/bignum/test_mul.rb53
6 files changed, 145 insertions, 0 deletions
diff --git a/ChangeLog b/ChangeLog
index ad97dd8020..2d83c9aeb1 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,13 @@
+Sun Jul 7 22:59:06 2013 Tanaka Akira <akr@fsij.org>
+
+ * internal.h (rb_big_mul_normal): Declared.
+ (rb_big_mul_balance): Ditto.
+ (rb_big_mul_karatsuba): Ditto.
+
+ * bignum.c (rb_big_mul_normal): New function for tests.
+ (rb_big_mul_balance): Ditto.
+ (rb_big_mul_karatsuba): Ditto.
+
Sun Jul 7 19:21:30 2013 Tanaka Akira <akr@fsij.org>
* bignum.c: Reorder functions to decrease forward reference.
diff --git a/bignum.c b/bignum.c
index ea828ff859..31d35b2d78 100644
--- a/bignum.c
+++ b/bignum.c
@@ -1489,6 +1489,17 @@ bary_mul_normal(BDIGIT *zds, size_t zl, BDIGIT *xds, size_t xl, BDIGIT *yds, siz
}
}
+VALUE
+rb_big_mul_normal(VALUE x, VALUE y)
+{
+ size_t xn = RBIGNUM_LEN(x), yn = RBIGNUM_LEN(y), zn = xn + yn;
+ VALUE z = bignew(zn, RBIGNUM_SIGN(x)==RBIGNUM_SIGN(y));
+ bary_mul_normal(BDIGITS(z), zn, BDIGITS(x), xn, BDIGITS(y), yn);
+ RB_GC_GUARD(x);
+ RB_GC_GUARD(y);
+ return z;
+}
+
/* efficient squaring (2 times faster than normal multiplication)
* ref: Handbook of Applied Cryptography, Algorithm 14.16
* http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf
@@ -1558,6 +1569,19 @@ bary_mul_balance(BDIGIT *zds, size_t zl, BDIGIT *xds, size_t xl, BDIGIT *yds, si
ALLOCV_END(work);
}
+VALUE
+rb_big_mul_balance(VALUE x, VALUE y)
+{
+ size_t xn = RBIGNUM_LEN(x), yn = RBIGNUM_LEN(y), zn = xn + yn;
+ VALUE z = bignew(zn, RBIGNUM_SIGN(x)==RBIGNUM_SIGN(y));
+ if (!(2 * xn <= yn || 3 * xn <= 2*(yn+2)))
+ rb_raise(rb_eArgError, "invalid bignum length");
+ bary_mul_balance(BDIGITS(z), zn, BDIGITS(x), xn, BDIGITS(y), yn);
+ RB_GC_GUARD(x);
+ RB_GC_GUARD(y);
+ return z;
+}
+
/* multiplication by karatsuba method */
static void
bary_mul_karatsuba(BDIGIT *zds, size_t zl, BDIGIT *xds, size_t xl, BDIGIT *yds, size_t yl)
@@ -1720,6 +1744,19 @@ bary_mul_karatsuba(BDIGIT *zds, size_t zl, BDIGIT *xds, size_t xl, BDIGIT *yds,
ALLOCV_END(work);
}
+VALUE
+rb_big_mul_karatsuba(VALUE x, VALUE y)
+{
+ size_t xn = RBIGNUM_LEN(x), yn = RBIGNUM_LEN(y), zn = xn + yn;
+ VALUE z = bignew(zn, RBIGNUM_SIGN(x)==RBIGNUM_SIGN(y));
+ if (!(xn <= yn && yn < 2 * xn))
+ rb_raise(rb_eArgError, "invalid bignum length");
+ bary_mul_karatsuba(BDIGITS(z), zn, BDIGITS(x), xn, BDIGITS(y), yn);
+ RB_GC_GUARD(x);
+ RB_GC_GUARD(y);
+ return z;
+}
+
static void
bary_mul1(BDIGIT *zds, size_t zl, BDIGIT *xds, size_t xl, BDIGIT *yds, size_t yl)
{
diff --git a/ext/-test-/bignum/depend b/ext/-test-/bignum/depend
index 8524e41ce6..c8ddefb6fb 100644
--- a/ext/-test-/bignum/depend
+++ b/ext/-test-/bignum/depend
@@ -1,3 +1,4 @@
$(OBJS): $(HDRS) $(ruby_headers)
pack.o: pack.c $(top_srcdir)/internal.h
+mul.o: mul.c $(top_srcdir)/internal.h
diff --git a/ext/-test-/bignum/mul.c b/ext/-test-/bignum/mul.c
new file mode 100644
index 0000000000..18ab3f7633
--- /dev/null
+++ b/ext/-test-/bignum/mul.c
@@ -0,0 +1,41 @@
+#include "ruby.h"
+#include "internal.h"
+
+static VALUE
+big(VALUE x)
+{
+ if (FIXNUM_P(x))
+ return rb_int2big(FIX2LONG(x));
+ if (RB_TYPE_P(x, T_BIGNUM))
+ return x;
+ rb_raise(rb_eTypeError, "can't convert %s to Bignum",
+ rb_obj_classname(x));
+}
+
+static VALUE
+mul_normal(VALUE x, VALUE y)
+{
+ return rb_big_norm(rb_big_mul_normal(big(x), big(y)));
+}
+
+static VALUE
+mul_balance(VALUE x, VALUE y)
+{
+ return rb_big_norm(rb_big_mul_balance(big(x), big(y)));
+}
+
+static VALUE
+mul_karatsuba(VALUE x, VALUE y)
+{
+ return rb_big_norm(rb_big_mul_karatsuba(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_mul_balance", mul_balance, 1);
+ rb_define_method(rb_cInteger, "big_mul_karatsuba", mul_karatsuba, 1);
+}
diff --git a/internal.h b/internal.h
index 6390277dd3..38e3701059 100644
--- a/internal.h
+++ b/internal.h
@@ -515,6 +515,9 @@ VALUE rb_thread_io_blocking_region(rb_blocking_function_t *func, void *data1, in
/* bignum.c */
int rb_integer_pack(VALUE val, void *words, size_t numwords, size_t wordsize, size_t nails, int flags);
VALUE rb_integer_unpack(const void *words, size_t numwords, size_t wordsize, size_t nails, int flags);
+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);
/* io.c */
void rb_maygvl_fd_fix_cloexec(int fd);
diff --git a/test/-ext-/bignum/test_mul.rb b/test/-ext-/bignum/test_mul.rb
new file mode 100644
index 0000000000..ad3b38febd
--- /dev/null
+++ b/test/-ext-/bignum/test_mul.rb
@@ -0,0 +1,53 @@
+require 'test/unit'
+require "-test-/bignum"
+
+class TestBignum < Test::Unit::TestCase
+ class TestMul < Test::Unit::TestCase
+
+ SIZEOF_BDIGITS = Bignum::SIZEOF_BDIGITS
+ BITSPERDIG = Bignum::BITSPERDIG
+
+ def test_mul_normal
+ x = (1 << BITSPERDIG) | 1
+ y = (1 << BITSPERDIG) | 1
+ z = (1 << (BITSPERDIG*2)) | (2 << BITSPERDIG) | 1
+ assert_equal(z, x.big_mul_normal(y))
+ end
+
+ def test_mul_normal_zero_in_x
+ x = (1 << (2*BITSPERDIG)) | 1
+ y = (1 << BITSPERDIG) | 1
+ z = (1 << (BITSPERDIG*3)) | (1 << (BITSPERDIG*2)) | (1 << BITSPERDIG) | 1
+ assert_equal(z, x.big_mul_normal(y))
+ end
+
+ def test_mul_normal_zero_in_y
+ x = (1 << BITSPERDIG) | 1
+ y = (1 << (2*BITSPERDIG)) | 1
+ z = (1 << (BITSPERDIG*3)) | (1 << (BITSPERDIG*2)) | (1 << BITSPERDIG) | 1
+ assert_equal(z, x.big_mul_normal(y))
+ end
+
+ def test_mul_normal_max_max
+ x = (1 << (2*BITSPERDIG)) - 1
+ y = (1 << (2*BITSPERDIG)) - 1
+ z = (1 << (4*BITSPERDIG)) - (1 << (2*BITSPERDIG+1)) + 1
+ assert_equal(z, x.big_mul_normal(y))
+ end
+
+ def test_mul_balance
+ x = (1 << BITSPERDIG) | 1
+ y = (1 << BITSPERDIG) | 1
+ z = (1 << (BITSPERDIG*2)) | (2 << BITSPERDIG) | 1
+ assert_equal(z, x.big_mul_balance(y))
+ end
+
+ def test_mul_karatsuba
+ x = (1 << BITSPERDIG) | 1
+ y = (1 << BITSPERDIG) | 1
+ z = (1 << (BITSPERDIG*2)) | (2 << BITSPERDIG) | 1
+ assert_equal(z, x.big_mul_karatsuba(y))
+ end
+
+ end
+end
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-08 22:03:58 +0000