e$B1sF#$H?=$7$^$9!#e(B
Karatsuba e$B$N4p?tJQ49%"%k%4%j%:%`$Ge(B Bignum#to_s
e$B$r9bB.2=$9$k%Q%C%A$re(B
e$B=q$-$^$7$?!#2?@i7e$b$"$k$h$&$JBg$-$Je(B Bignum
e$B$NI=<($,B.$/$J$j$^$9!#e(B
(e$B$=$&$$$&$3$H$r$7$?$$$3$H$,$I$N$/$i$$$"$k$N$+$O$o$+$j$^$;$s$,e(B)
e$B?tCM1i;;$N%"%k%4%j%:%`$O;d$b6l<j$J$N$G%P%0$,$"$k$+$b$7$l$^$;$s$,!"e(B
e$B$?$?$-Bf$K$G$b$J$l$P$H;W$$$^$9!#$h$m$7$1$l$P:NMQ$r$48!F$$/$@$5$$!#e(B
$ ruby -e ‘100.times { puts “puts((#{ rand(50000) }**#{ rand(50000)
}).to_s(#{ rand(35) + 2 }))” }’ > test_bignum.rb
$ head test_bignum.rb
puts((2942121521).to_s(10))
puts((1449743375).to_s(7))
puts((199114216).to_s(23))
puts((791541353).to_s(27))
puts((2273633284).to_s(6))
puts((2435425848).to_s(16))
puts((285417140).to_s(29))
puts((261823001).to_s(14))
puts((493423263).to_s(26))
puts((2956510694).to_s(29))
$ time ./ruby.org test_bignum.rb > result.org.txt # e$B%Q%C%AA0e(B
real 16m58.310s
user 0m19.590s
sys 16m35.400s
$ time ./ruby.new test_bignum.rb > result.new.txt # e$B%Q%C%A8ee(B
real 2m47.719s
user 0m5.820s
sys 2m41.090s
Karatsuba
e$B$N4p?tJQ49%"%k%4%j%:%`$O!";d$NM}2r$G$O0J2<$N$h$&$J$b$N$G$9!#e(B
e$BIaDL$N%"%k%4%j%:%`$G$O!"e(B10
e$B$G3d$j$^$/$C$F3F=|;;$G$NM>$j$rJ8;zNs$K$7$^$9e(B
(e$B:#$Ne(B Ruby e$B$Ne(B Bignum#to_s e$B$N<BAu$b$=$&$J$C$F$$$^$9e(B)
e$B!#$3$N$H$-e(B 1 e$B2s$Ne(B
e$B=|;;$N7W;;NL$O3d$i$l$k?t$N7e?t$KBP$7$F@~7A$N;~4V$,$+$+$k$?$a!"A4BN$G$Oe(B
O(n^2) e$B$N;~4V$,$+$+$j$^$9!#e(B
Karatsuba e$B$N4p?tJQ49%"%k%4%j%:%`$G$O!"e(B10
e$B$NN_>h?t$G!"7e?t$r$*$h$=H>J,$Ke(B
e$B$9$k$h$&$JCM$G3d$j$^$/$j$^$9!#e(B12345678 e$B$NNc$G9M$($k$H!"e(B
12345678 (e$B$re(B 10000 e$B$G3d$ke(B)
-> 1234 e$B$He(B 5678 (e$B$r$=$l$>$le(B 100 e$B$G3d$ke(B)
-> 12 e$B$He(B 34 e$B$He(B 56 e$B$He(B 78 (e$B$r$=$l$>$le(B 10
e$B$G3d$ke(B)
-> 1 e$B$He(B 2 e$B$He(B 3 e$B$He(B 4 e$B$He(B 5 e$B$He(B 6 e$B$He(B 7
e$B$He(B 8
e$B$H$J$j!“3F?t;z$,J8;zNs$H$J$j$^$9!#=|;;2s?t$OIaDL$N%”%k%4%j%:%$HF1$8e(B e$B$G$9$,!"3F=|;;$G$N3d$i$l$k?t$N7e?t$,8:$C$F$$$k$?$a!"A4BN$H$7$F$Oe(B O(n log n) e$B$N;~4V$G$9$$h$&$G$9!#e(B
Index: bignum.c
— bignum.c (revision 12854)
+++ bignum.c (working copy)
@@ -595,11 +595,97 @@
}
const char ruby_digitmap[] = “0123456789abcdefghijklmnopqrstuvwxyz”;
+static inline int
+big2str_normal(VALUE x, long j, int base, int hbase, char *s, int trim)
+{
- long i = RBIGNUM(x)->len;
- BDIGIT *ds = BDIGITS(x);
- while (i && j > 1) {
-
long k = i; -
BDIGIT_DBL num = 0; -
while (k--) { -
num = BIGUP(num) + ds[k]; -
ds[k] = (BDIGIT)(num / hbase); -
num %= hbase; -
} -
if (trim && ds[i-1] == 0) i--; -
k = SIZEOF_BDIGITS; -
while (k--) { -
s[--j] = ruby_digitmap[num % base]; -
num /= base; -
if (!trim && j < 1) break; -
if (trim && i == 0 && num == 0) break; -
} - }
- return j;
+}
+#define KARATSUBA_DIGITS 1024
+static VALUE big2str_table[37][16];
+
+static VALUE bigsqr(VALUE x);
+static void bigdivmod(VALUE x, VALUE y, VALUE *divp, VALUE *modp);
+
+static inline int
+big2str_karatsuba(VALUE x, int n, int base, int hbase, char *s, int
trim)
+{
- long i, j, k, bs_len, sign = RBIGNUM(x)->sign;
- volatile VALUE t = big2str_table[base][0], t2;
- VALUE *as, *bs, q, r;
- j = RBIGNUM(t)->len;
- for (i=0; j <= RBIGNUM(x)->len; i++) j *= 2;
- as = ALLOCA_N(VALUE, i);
- for (i=0,j=1; ; i++,j*=2) {
-
as[i] = t; -
if(big2str_table[base][i + 1]) { -
t2 = big2str_table[base][i + 1]; -
} -
else { -
t2 = bigsqr(t); -
if(i + 1 < 16) { -
big2str_table[base][i + 1] = t2; -
rb_global_variable(&big2str_table[base][i + 1]); -
} -
} -
if(RBIGNUM(x)->len < RBIGNUM(t2)->len) break; -
t = t2; - }
- bs_len = j * 2;
- bs = ALLOCA_N(VALUE, bs_len);
- bs[0] = x;
- RBIGNUM(x)->sign = 1;
- for (; j>0; i–, j/=2) {
-
for (k=0; k<bs_len; k+=j*2) { -
bigdivmod(bs[k], as[i], &q, &r); -
bs[k] = q; -
bs[k + j] = r; -
} - }
- RBIGNUM(x)->sign = sign;
- j = 0;
- while(RBIGNUM(bs[j])->len == 1 && BDIGITS(bs[j])[0] == 0) j++;
- for (i=bs_len-1; i>j; i–) {
-
k = big2str_normal( -
bs[i], KARATSUBA_DIGITS, base, hbase, -
s + n - KARATSUBA_DIGITS, Qfalse); -
n -= KARATSUBA_DIGITS - k; - }
- n = big2str_normal(bs[j], n, base, hbase, s, trim);
- return n;
+}
VALUE
rb_big2str0(VALUE x, int base, int trim)
{
volatile VALUE t;
-
BDIGIT *ds;
long i, j, hbase;
VALUE ss;
char *s;
@@ -646,29 +732,16 @@
#endift = rb_big_clone(x);
-
ds = BDIGITS(t);
ss = rb_str_new(0, j+1);
s = RSTRING_PTR(ss);s[0] = RBIGNUM(x)->sign ? ‘+’ : ‘-’;
-
while (i && j > 1) {
-
long k = i; -
BDIGIT_DBL num = 0; -
while (k--) { -
num = BIGUP(num) + ds[k]; -
ds[k] = (BDIGIT)(num / hbase); -
num %= hbase; -
} -
if (trim && ds[i-1] == 0) i--; -
k = SIZEOF_BDIGITS; -
while (k--) { -
s[--j] = ruby_digitmap[num % base]; -
num /= base; -
if (!trim && j < 1) break; -
if (trim && i == 0 && num == 0) break; -
}
- if (RBIGNUM(x)->len > RBIGNUM(big2str_table[base][0])->len * 4) {
-
}j = big2str_karatsuba(t, j, base, hbase, s, trim); - else {
-
j = big2str_normal(t, j, base, hbase, s, trim); - }
if (trim) {while (s[j] == ‘0’) j++;}
i = RSTRING_LEN(ss) - j;
if (RBIGNUM(x)->sign) {
@@ -683,6 +756,22 @@
return ss;
}
+static void
+init_big2str_table(void)
+{
- int i, j;
- VALUE v;
- for (i=0; i<37; i++) {
-
v = rb_big_pow(rb_int2big(i), INT2FIX(KARATSUBA_DIGITS)); -
big2str_table[i][0] = v; -
rb_global_variable(&big2str_table[i][0]); -
for (j=1; j<16; j++) { -
big2str_table[i][j] = Qfalse; -
} - }
+}
VALUE
rb_big2str(VALUE x, int base)
{
@@ -2215,4 +2304,6 @@
rb_define_method(rb_cBignum, “to_f”, rb_big_to_f, 0);
rb_define_method(rb_cBignum, “abs”, rb_big_abs, 0);
rb_define_method(rb_cBignum, “size”, rb_big_size, 0);
+
- init_big2str_table();
}