ruby-changes:29772
From: akr <ko1@a...>
Date: Sun, 7 Jul 2013 23:02:36 +0900 (JST)
Subject: [ruby-changes:29772] akr:r41824 (trunk): * internal.h (rb_big_mul_normal): Declared.
akr 2013-07-07 23:01:40 +0900 (Sun, 07 Jul 2013) New Revision: 41824 http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=rev&revision=41824 Log: * 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. Added files: trunk/ext/-test-/bignum/mul.c trunk/test/-ext-/bignum/test_mul.rb Modified files: trunk/ChangeLog trunk/bignum.c trunk/ext/-test-/bignum/depend trunk/internal.h Index: ChangeLog =================================================================== --- ChangeLog (revision 41823) +++ ChangeLog (revision 41824) @@ -1,3 +1,13 @@ https://github.com/ruby/ruby/blob/trunk/ChangeLog#L1 +Sun Jul 7 22:59:06 2013 Tanaka Akira <akr@f...> + + * 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@f...> * bignum.c: Reorder functions to decrease forward reference. Index: ext/-test-/bignum/depend =================================================================== --- ext/-test-/bignum/depend (revision 41823) +++ ext/-test-/bignum/depend (revision 41824) @@ -1,3 +1,4 @@ https://github.com/ruby/ruby/blob/trunk/ext/-test-/bignum/depend#L1 $(OBJS): $(HDRS) $(ruby_headers) pack.o: pack.c $(top_srcdir)/internal.h +mul.o: mul.c $(top_srcdir)/internal.h Index: ext/-test-/bignum/mul.c =================================================================== --- ext/-test-/bignum/mul.c (revision 0) +++ ext/-test-/bignum/mul.c (revision 41824) @@ -0,0 +1,41 @@ https://github.com/ruby/ruby/blob/trunk/ext/-test-/bignum/mul.c#L1 +#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); +} Property changes on: ext/-test-/bignum/mul.c ___________________________________________________________________ Added: svn:eol-style + LF Index: internal.h =================================================================== --- internal.h (revision 41823) +++ internal.h (revision 41824) @@ -515,6 +515,9 @@ VALUE rb_thread_io_blocking_region(rb_bl https://github.com/ruby/ruby/blob/trunk/internal.h#L515 /* 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); Index: bignum.c =================================================================== --- bignum.c (revision 41823) +++ bignum.c (revision 41824) @@ -1489,6 +1489,17 @@ bary_mul_normal(BDIGIT *zds, size_t zl, https://github.com/ruby/ruby/blob/trunk/bignum.c#L1489 } } +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, https://github.com/ruby/ruby/blob/trunk/bignum.c#L1569 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 z https://github.com/ruby/ruby/blob/trunk/bignum.c#L1744 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) { Index: test/-ext-/bignum/test_mul.rb =================================================================== --- test/-ext-/bignum/test_mul.rb (revision 0) +++ test/-ext-/bignum/test_mul.rb (revision 41824) @@ -0,0 +1,53 @@ https://github.com/ruby/ruby/blob/trunk/test/-ext-/bignum/test_mul.rb#L1 +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 Property changes on: test/-ext-/bignum/test_mul.rb ___________________________________________________________________ Added: svn:eol-style + LF -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/