高速 Bignum#to_s

Bignum と戯れていて気がつきましたが、とても大きい値は表示するだけでかなり遅いです。65536**65536 (300,000 桁くらい) で 71 秒とか。Ctrl+C で止められないのでいらいらします。

$ time ruby -e 'p(65536**65536)' > r1.txt

real    1m10.802s
user    0m4.580s
sys     1m6.190s
$ wc -c r1.txt
315654 r1.txt

どうも Bignum#to_s の基数変換に時間がかかりまくってるみたいです。実装を一瞬だけ見てみたところ、O(n^2) のアルゴリズムになっているような気がしました。
そこで Karatsuba の基数変換アルゴリズム みたいなものを実装してみました。O(n log n) のはず。

$ time ruby -rkrc -e 'p(65536**65536)' > r2.txt

real    0m16.113s
user    0m2.310s
sys     0m13.810s
$ diff r1.txt r2.txt
$

16 秒。だいぶ早くなりました。まだ遅いけど。以下ソース。

数値演算のコードはいかにもバグが入ってそうで、自信は全くありません。テストもろくにしてません。

class Bignum
    alias to_s_org to_s

    MIN_DIGITS = 1024
    THRESHOLDS = (0..36).map {|b| b ** MIN_DIGITS }

    def to_s(b = 10)
        t = THRESHOLDS[b]
        return to_s_org(b) if self < t

        a = [t]
        while self > t2 = t * t
            a << t = t2
        end
        d = [self]
        a.reverse_each do |t|
            d = d.map {|x| x.divmod(t) }.flatten
            d.shift if d.first == 0
        end
        s = d.shift.to_s(b)
        s << d.map {|x| x.to_s(b).rjust(MIN_DIGITS, "0") }.join
    end
end

基数が 16 のときはかなり速くなるようです。65536**65536 で 37 秒が 0.25 秒に。

$ time ruby -e '(65536**65536).to_s(16)'
real    0m36.917s
user    0m2.920s
sys     0m33.930s
$ time ruby -rkrc -e '(65536**65536).to_s(16)'

real    0m0.254s
user    0m0.150s
sys     0m0.100s

ただし小さい値のときは逆に若干遅くなります。1000**1000 で 0.042 秒が 0.089 秒に。閾値がよくないのかな。C で書けばいいだけ？

$ time ruby -e '(1000**1000).to_s'

real    0m0.042s
user    0m0.030s
sys     0m0.010s
$ time ruby -rkrc -e '(1000**1000).to_s'

real    0m0.089s
user    0m0.070s
sys     0m0.010s