2010年12月 3日

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

むらたです。

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@xxxxx
twitter: http://twitter.com/mrkn/
blog: http://d.hatena.ne.jp/mrkn/

投稿者 xml-rpc : 2010年12月 3日 16:52
役に立ちました?:
過去のフィードバック 平均:(0) 総合:(0) 投票回数:(0)
本記事へのTrackback: http://hoop.euqset.org/blog/mt-tb2006.cgi/100457
トラックバック
コメント
コメントする




画像の中に見える文字を入力してください。