在Haskell中实现Karatsuba算法

Question

我刚刚了解了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位甚至更大的数字时，它比正常情况下的*慢很多。我该如何改进这个算法呢？

- Tengu

---

这个 base =10^((length . show $ max x y) div 2) 不好。虽然 GHC 对于 Integer 的 Show 实例比 Java 的 BigInteger.toString() 或 Python 的 str 在处理大数时要快得多，但仍然相当慢（想想它必须做什么）。你应该在那里使用 GHC.Float.integerLogBase 来获得一个不错的加速效果。如果你使用一个 2 的幂作为基数，那就更好了。 - Daniel Fischer

Answer 1

实际上，我怀疑你无法提高性能以打败朴素的运算符 - 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。

- zw324

---

谢谢你的回答。我明白了。那么，我的算法还不错，只是 * 真的很快吗？ - Tengu

可能是这样，至少这是我的想法。我几年前使用过GMP，并发现它非常棒。它似乎有很多算法和尖端研究思路，因此我不会轻易地期望它被超越。 - zw324

我明白了。实现算法是一个不错的练习。谢谢你的回答。 - Tengu

GMP使用以下算法进行整数乘法（按输入数字的大小排序）：1.朴素（学校）算法，2.Karatsuba，3.Toom 3-Way，4.Toom 4-Way，5.更高阶Toom'n'Half，6.快速傅里叶变换乘法。 - dnaq

http://gmplib.org/manual/Multiplication-Algorithms.html#Multiplication-Algorithms - dnaq