在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位数甚至更大的数字时,这比平常慢很多.我怎么能改进这个算法？

Answer 1

实际上我怀疑你可以提高性能以击败天真的操作员 - Haskell 在引擎盖下使用GMP,当算法适用于值范围时,它应该自动使用Toom-3或其他算法.天真的Karatsuba可能甚至没有使用,但据说Toom系列在算法上接近它.如果你考虑一下,GHC没有理由不使用一些先进的算法进行乘法,因为他们已经开箱即用.

我最后一次检查时,GMP速度非常快,即使在正常的双倍范围内使用,也至少和gcc的编译结果一样快.

有一项关于从GHC中删除GMP 的建议,但似乎相当不活跃.

编辑:感谢@danvari,以下是GMP使用的不同算法:http://gmplib.org/manual/Multiplication-Algorithms.html#Multiplication-Algorithms .当数字足够小时,似乎可以使用Karatsuba,除了通常的Toom-Cook系列之外,还使用了FFT.