# Faster Bignum#to_s

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

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\$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();
}

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