ruby-list

むらたです。

Bignum#* を Toom3 乗法 (r=2 の Toom-Cook 乗法) に対応させる patch を作りました。
svn trunk の r29883 をベースに開発していましたが、r29965 にも適用可能でした。
patch は以下の gist に投稿してあります。
https://gist.github.com/726653

n ビット数同士の乗算10回分の計算時間を 1.9.2p80 と比較すると以下のようになります。
1千万ビット数同士の乗算において2倍強の高速化が実現できています。

  ------------------------------------------
      n [bit]   1.9.2p80 [sec]   Toom3 [sec]
  ------------------------------------------
            1                0             0
      100_000             0.04          0.04
      500_000             0.44          0.36
    1_000_000             1.33          0.88
    5_000_000            18.98         11.28
   10_000_000            60.50         28.82
   50_000_000           705.13        332.78
  100_000_000          2119.45        946.28
  ------------------------------------------

使用したマシンのスペックは以下のとおりです。
OS: Mac OS X 10.6.5
CPU: Core i7 2.66GHz
MEM: 8GB

この patch では Karatsuba 乗法から切り替える桁数の閾値 TOOM3_MUL_DIGITS を150に
設定しています。この値が最適かどうかはこれから調査します。

Toom3 乗法に対応させて乗算が高速化されることで、除算と冪乗が間接的に高速化されます。
すると、Rational が内部で行ってる通分や、prime.rb で実装されている素因数分解などの
高速化を実現できます。

上の patch にはデバッグ用のコードが混ざってるので、
取り込んで良ければ、それらを消した patch をマージしてコミットしたいです。

ご検討していただけますでしょうか。

-- 
Kenta Murata
OpenPGP FP = 1D69 ADDE 081C 9CC2 2E54  98C1 CEFE 8AFB 6081 B062

本を書きました!!
『Ruby 逆引きレシピ』 http://www.amazon.co.jp/dp/4798119881/mrkn-22

E-mail: mrkn@mrkn.jp
twitter: http://twitter.com/mrkn/
blog: http://d.hatena.ne.jp/mrkn/

Thread

Prev Next

In This Thread

Prev Next

[#47667] 文字列中に含まれる 8 進数表記 "\nnn" というパターンに正規表現でマッチさせたい — Kensuke Kaneko <kyanny@...>

[#47674] Rubyist忘年会2010のおしらせ — takkanm@...

[#47675] Bignum#* を Toom3 乗法に対応させる patch — Kenta Murata <muraken@...>

[#47679] [ANN]第4回ぐんまRubyの勉強会(guRuby)のご案内 — Yuichi NANSAI <nansai@...>

[#47684] ネットワークに流れるパケットのキャプチャーについて。 — Tetsuo Beppu <anfojp@...>

[#47693] Array#values_at behavior — Nobuhiro IMAI <nov@...>

[#47694] [ANN] spreadsheet 0.6.5 リリース — Masaomi Hatakeyama <mhatakeyama@...>

[#47700] ruby 1.9 では Module.constants で参照できない名前が返ってくる — "KISHIMOTO, Makoto" <ksmakoto@...4u.or.jp>

[#47701] super の引数 — "Takashi SUGA" <suchowan@...>

[#47703] [ANN]第49回とちぎRubyの勉強会(toRuby)のご案内 — 米澤 慎 <vestige@...3.so-net.ne.jp>

[#47705] Windows(CP932）でのRuby1.9のirbの実行について — 中川貴 <nora1962@...>

[#47707] [ANN]Miyako2.1.20リリース — cyross@...

[#47709] [ANN]とちぎRuby会議03のご案内(toRuby50回記念) — 米澤 慎 <vestige@...3.so-net.ne.jp>

[#47710] [ANN] Ruby 1.8.7 patchlevel 330 released — Urabe Shyouhei <shyouhei@...>

[#47711] [ANN] Ruby 1.9.2リリース — "Yuki Sonoda (Yugui)" <yugui@...>

[#47712] [ANN]ASR 1.8.7-p330版リリース — arton <artonx@...>

[#47713] [ANN]東京Ruby会議05開催のお知らせ — "KOSHIBA Toshiaki(so-net)" <koshiba@...8.so-net.ne.jp>

[#47715] Windowsで1.9.2p136＋zlibのインストール — AOKI Yoshihiro <aoki@...>

[#47724] Ruby on Railsセミナー「2011年はRails3を使おう」〜masuidriveに学ぶ — 川井健史 <takeshi.kawai@...>

[#47727] Date.parse("2010-12") がv1.8.7 でエラー — naopontan <naopontan@...>

[#47733] 第 48 回 Ruby/Rails勉強会@関西を開催します。 — muryoimpl <muryoimpl@...>

[#47735] 「Rubyリファレンスマニュアル刷新計画」2010-12分のスナップショットリリース — okkez <okkez000@...>

[#47737] [ANN] Rabbit 0.9.2 — Kouhei Sutou <kou@...>

[ruby-list:47675] Bignum#* を Toom3 乗法に対応させる patch

Thread

In This Thread

[#47703] [ANN]第49回とちぎRubyの勉強会(toRuby)のご案内 — 米澤慎 <vestige@...3.so-net.ne.jp>

[#47709] [ANN]とちぎRuby会議03のご案内(toRuby50回記念) — 米澤慎 <vestige@...3.so-net.ne.jp>