From: Yusuke ENDOH <mame@...>
Date: 2007-12-19T12:49:02+09:00
Subject: [ruby-dev:32632] Re: faster Bignum#*

遠藤です。

07/12/19 に Yukihiro Matsumoto<matz@ruby-lang.org> さんは書きました:
> まつもと ゆきひろです
>
> In message "Re: [ruby-dev:32629] faster Bignum#*"
>    on Wed, 19 Dec 2007 00:18:17 +0900, "Yusuke ENDOH" <mame@tsg.ne.jp> writes:
>
> |Bignum#* に FFT を用いた乗算を実装してみました。
> |10 進で 100000 桁以上あるような巨大な整数の乗算が速くなります。
> |そんな需要はないでしょうか。
>
> うーん、あるのかな。クリスマスが終わってから取り込む方向で考
> えます。

多倍長整数演算は円周率の計算とかライフゲームとかに使えるので、怪しい
需要はたまにあります (笑)

とりあえず、巨大な整数の乗算や to_s をしたとき Ctrl-C がきかなくなる
のはなんとかしといたら嬉しいと思います。
そこで大きい数の rb_big_mul0 と divrem を rb_thread_blocking_region で
実行するパッチを書いてみました。どうでしょうか。


Index: bignum.c
===================================================================
--- bignum.c	(revision 14313)
+++ bignum.c	(working copy)
@@ -1442,34 +1442,32 @@
     }
 }

+static void
+rb_big_stop(void *ptr)
+{
+    VALUE *stop = (VALUE*)ptr;
+    *stop = Qtrue;
+}
+
+struct big_mul_struct {
+    VALUE x, y, stop;
+};
+
 static VALUE
-rb_big_mul0(VALUE x, VALUE y)
+bigmul1(void *ptr)
 {
+    struct big_mul_struct *bms = (struct big_mul_struct*)ptr;
     long i, j;
     BDIGIT_DBL n = 0;
-    VALUE z;
+    VALUE x = bms->x, y = bms->y, z;
     BDIGIT *zds;

-    switch (TYPE(y)) {
-      case T_FIXNUM:
-	y = rb_int2big(FIX2LONG(y));
-	break;
-
-      case T_BIGNUM:
-	break;
-
-      case T_FLOAT:
-	return DOUBLE2NUM(rb_big2dbl(x) * RFLOAT_VALUE(y));
-
-      default:
-	return rb_num_coerce_bin(x, y);
-    }
-
     j = RBIGNUM_LEN(x) + RBIGNUM_LEN(y) + 1;
     z = bignew(j, RBIGNUM_SIGN(x)==RBIGNUM_SIGN(y));
     zds = BDIGITS(z);
     while (j--) zds[j] = 0;
     for (i = 0; i < RBIGNUM_LEN(x); i++) {
+	if (bms->stop) return Qnil;
 	BDIGIT_DBL dd = BDIGITS(x)[i];
 	if (dd == 0) continue;
 	n = 0;
@@ -1486,6 +1484,42 @@
     return z;
 }

+static VALUE
+rb_big_mul0(VALUE x, VALUE y)
+{
+    struct big_mul_struct bms;
+    VALUE z;
+
+    switch (TYPE(y)) {
+      case T_FIXNUM:
+	y = rb_int2big(FIX2LONG(y));
+	break;
+
+      case T_BIGNUM:
+	break;
+
+      case T_FLOAT:
+	return DOUBLE2NUM(rb_big2dbl(x) * RFLOAT_VALUE(y));
+
+      default:
+	return rb_num_coerce_bin(x, y);
+    }
+
+    bms.x = x;
+    bms.y = y;
+    bms.stop = Qfalse;
+
+    if (RBIGNUM_LEN(x) + RBIGNUM_LEN(y) > 10000) {
+	VALUE stop = Qfalse;
+	z = rb_thread_blocking_region(bigmul1, &bms, rb_big_stop, &bms.stop);
+    }
+    else {
+	z = bigmul1(&bms);
+    }
+
+    return z;
+}
+
 /*
  *  call-seq:
  *     big * other  => Numeric
@@ -1499,9 +1533,15 @@
     return bignorm(rb_big_mul0(x, y));
 }

-static void
-bigdivrem(VALUE x, VALUE y, VALUE *divp, VALUE *modp)
+struct big_div_struct {
+    VALUE x, y, *divp, *modp, stop;
+};
+
+static VALUE
+bigdivrem1(void *ptr)
 {
+    struct big_div_struct *bds = (struct big_div_struct*)ptr;
+    VALUE x = bds->x, y = bds->y, *divp = bds->divp, *modp = bds->modp;
     long nx = RBIGNUM_LEN(x), ny = RBIGNUM_LEN(y);
     long i, j;
     VALUE yy, z;
@@ -1575,6 +1615,7 @@

     j = nx==ny?nx+1:nx;
     do {
+	if (bds->stop) return Qnil;
 	if (zds[j] ==  yds[ny-1]) q = BIGRAD-1;
 	else q = (BDIGIT)((BIGUP(zds[j]) + zds[j-1])/yds[ny-1]);
 	if (q) {
@@ -1627,6 +1668,27 @@
     }
 }

+static VALUE
+bigdivrem(VALUE x, VALUE y, VALUE *divp, VALUE *modp)
+{
+    struct big_div_struct bds;
+    VALUE z;
+
+    bds.x = x;
+    bds.y = y;
+    bds.divp = divp;
+    bds.modp = modp;
+    bds.stop = Qfalse;
+    if (RBIGNUM_LEN(x) > 10000 || RBIGNUM_LEN(y) > 10000) {
+	VALUE stop = Qfalse;
+	z = rb_thread_blocking_region(bigdivrem1, &bds, rb_big_stop, &bds.stop);
+    }
+    else {
+	z = bigdivrem1(&bds);
+    }
+    return z;
+}
+
 static void
 bigdivmod(VALUE x, VALUE y, VALUE *divp, VALUE *modp)
 {

-- 
Yusuke ENDOH <mame@tsg.ne.jp>