From: Kenta Murata <muraken@...>
Date: 2010-12-03T16:56:24+09:00
Subject: [ruby-dev:42677] Fwd: [ruby-list:47675] Bignum#* 	を Toom3 	乗法に対応させる patch

むらたです。

間違えて ruby-list に送ってしまったので、ruby-dev に送りなおします。

2010年12月3日16:52 Kenta Murata <muraken@gmail.com>:
> むらたです。
>
> 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/
>
>
>



-- 
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/