From: Kenta Murata Date: 2007-08-02T17:52:00+09:00 Subject: [ruby-dev:31338] Re: Bignum#to_s の Karatsuba 基数変換による高速化 むらけんです． On 8/1/07, Yusuke ENDOH wrote: > 1. 私のパッチは、数千桁以下の bignum に対してはオリジナルのルーチンを > 使うようにしています。むらけんさんのテストベンチで効果が出ないのは > 多分このためです。十数桁でも効果があることがあるんですね。 > > ただ閾値を大きくとったのには理由があります。Karatsuba のアルゴリズムは > 中途半端な長さの bignum に対して、逆に遅くなるからです。 そうなんですね．アルゴリズムの性質には詳しくなかったので勉強になります． 私も試してみましたが，十数桁の Bignum に対してはオリジナルの アルゴリズムの方が速いようですね．これは，ある桁数 N に対して，正数 M が 存在していて，N < M のときに素直に基数で割り算していく方が bigdivmod を 繰り返すより速いということなんでしょうかね？ > 2. 私のパッチは to_s が初めて呼ばれるまでテーブルを初期化しません。 > なので一回目の to_s は遅くなります。 > > # 遠藤パッチ版 > $ ./ruby -e '(x = 65536**65536).to_s; t = Time.new; x.to_s; p(Time.now - t)' > 8.390915 > > # むらけんさんパッチ版 > $ ./ruby -e '(x = 65536**65536).to_s; t = Time.new; x.to_s; p(Time.now - t)' > 10.460523 > > もうちょっと正確には、to_s(N) が呼ばれて初めて、必要なところだけ、 > 基数 N のテーブルを初期化する感じです (要するにあまりでかくない > bignum の to_s に迷惑をかけることはないつもり) 。 > > # ですが、むらけんさんのパッチはぱっと見テーブルを使ってない？ > # 改善の余地があるのかも。 一応，テーブルっぽいことはやっていますが，その部分が効率よく無いとは自分で も思っていました．そして，遠藤さんの変更部分を真剣に読ませていただきまして， ハッシュなんて使う必要なくて，素直に配列で管理できる事に気づきました． もう一つ，私の実装が素直に再帰を使って実装しているところを， 遠藤さんの実装はループに変換されいますね．どう見ても遠藤さんの実装のほうが 平均すると高速であるように見えます．私の実装は，基数ベキのキャッシュエントリ 数が遠藤さんの実装の2倍あるので，大きな桁数の変換を何度もやるときに有利 になったのだろうと思います． ということで，パッチは遠藤さんのバージョンを採用していただく方向でよいと思います． -- - Hide quoted text - Kenta Murata OpenPGP FP = FA26 35D7 4F98 3498 0810 E0D5 F213 966F E9EB 0BCC