Faster Bignum#to_s


#1

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((14497
43375).to_s(7))
puts((199114216).to_s(23))
puts((7915
41353).to_s(27))
puts((2273633284).to_s(6))
puts((24354
25848).to_s(16))
puts((285417140).to_s(29))
puts((2618
23001).to_s(14))
puts((493423263).to_s(26))
puts((29565
10694).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 @@
    #endif

    t = 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();
    }

#2

e$B1sF#$G$9!#JdB-$G$9!#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

trim e$B$N0UL#$,$h$/$o$+$i$J$+$C$?$N$G!"E,Ev$K<BAu$7$F$$$^$9!#e(B
e$B%*%j%8%J%k$N5sF0$r:F8=$G$-$F$$$J$$$+$b$7$l$^$;$s!#e(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

n e$B$O7e?t$G$9!#e(B