3

我刚刚了解了 Karatsuba 算法，并尝试在 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 或其他算法。天真的 Karatsuba 可能甚至不会被使用，但据说 Toom 系列在算法上接近它。如果你仔细想想，GHC 没有理由不使用一些高级算法进行乘法运算，因为他们已经开箱即用地支持它。

上次我检查时，GMP 非常快，即使在正常的 double 范围内使用，也至少与 gcc 的编译结果一样快。

有一个关于从 GHC 中删除 GMP 的建议，但它似乎相当不活跃。

编辑：感谢@danvari，这里是 GMP 使用的不同算法：http ://gmplib.org/manual/Multiplication-Algorithms.html#Multiplication-Algorithms 。当数字足够小时，似乎确实会使用 Karatsuba，并且除了通常的 Toom-Cook 系列之外，还使用了 FFT。

于 2013-06-07T17:38:39.620 回答