# Faster Bignum#to\_s

**URL:** <https://www.ruby-forum.com/t/faster-bignum-to-s/110667>\
**Category:** Development\
**Created:** [July 29, 2007, 5:05am UTC](https://www.ruby-forum.com/t/faster-bignum-to-s/110667 "2007-07-29T05:05:36Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![Yusuke\_ENDOH](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/y/c89c15/32.png) [@Yusuke\_ENDOH](https://www.ruby-forum.com/u/Yusuke_ENDOH)\
**Post date:** [July 29, 2007, 5:05am UTC](https://www.ruby-forum.com/t/faster-bignum-to-s/110667/1 "2007-07-29T05:05:36Z")

</div>

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((29421**21521).to\_s(10))  
puts((14497**43375).to\_s(7))  
puts((1991**14216).to\_s(23))  
puts((7915**41353).to\_s(27))  
puts((22736**33284).to\_s(6))  
puts((24354**25848).to\_s(16))  
puts((28541**7140).to\_s(29))  
puts((2618**23001).to\_s(14))  
puts((4934**23263).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

- ds = BDIGITS(t);  
ss = rb\_str\_new(0, j+1);  
s = RSTRING\_PTR(ss);

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

---

<div class="post-metadata">

**Author:** ![Yusuke\_ENDOH](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/y/c89c15/32.png) [@Yusuke\_ENDOH](https://www.ruby-forum.com/u/Yusuke_ENDOH)\
**Post date:** [July 29, 2007, 5:27am UTC](https://www.ruby-forum.com/t/faster-bignum-to-s/110667/2 "2007-07-29T05:27:38Z")

</div>

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