3

からつばアルゴリズムを知り、Haskellで実装してみました。

これが私のコードです：

(***) :: Integer -> Integer -> Integer
x *** y
    | max x y < ub = x*y    
    | otherwise =z2*base*base + ((x1+x0)***(y1+y0)-z2-z0)*base + z0
        where
            base =10^((length . show $ max x y) `div` 2)
            z2 =x1***y1
            z0 = x0***y0
            (x1, x0) = helper x
            (y1, y0) = helper y
            helper n = (n `div` base, n `mod` base)
            ub = 10000

これは、20 ～ 30 桁のような大きな数でチェックし、10 ～ 20 桁の十分な速さでチェックする限り、正確に機能します。*ただし、 100 桁またはそれ以上の数値の場合、これは通常よりもかなり遅くなります。このアルゴリズムを改善するにはどうすればよいですか?

4

1 に答える 1

8

実際、単純な演算子を打ち負かすためにパフォーマンスを改善できるとは思えません.Haskellは内部でGMPを使用しており、アルゴリズムが値の範囲でうまく機能する場合、Toom-3または他のアルゴリズムを自動的に使用する必要があります. ナイーブなカラツバは使わないかもしれませんが、トゥームシリーズはアルゴリズム的にそれに近いと言われています。考えてみれば、GHC が乗算に高度なアルゴリズムを使用しない理由はありません。

私が最後にチェックしたとき、GMPは非常に高速で、通常の2倍の範囲で使用しても、少なくともgccのコンパイル結果と同じくらい高速です.

GHC から GMP を削除するという提案がありますが、あまり活発ではないようです。

編集: @danvari のおかげで、GMP が使用するさまざまなアルゴリズムを次に示します: http://gmplib.org/manual/Multiplication-Algorithms.html#Multiplication-Algorithms。カラツバは数が少ないと慣れるそうで、通常のToom-Cookファミリーの他にFFTも使われています。

于 2013-06-07T17:38:39.620 に答える