Implementing Karatsuba algorithm in Haskell

Question

I just got to know about Karatsuba Algorithm, and I tried to implement it in Haskell.

Here is my code:

(***) :: 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

This works accurately as long as I checked with large numbers like 20 -30 digits and fast enough for 10-20 digits. However, this is a a lot slower than normal * when 100 digits or even bigger numbers. How I can improve this algorithm?

Answer 1

Actually I doubt you could improve the performance to beat the naive operator - Haskell use GMP under the hood, which should automatically use Toom-3 or other algorithms when the algorithm works well for the value range. The naive Karatsuba might not be even used, but the Toom series is said to be algorithmically close to it. If you come to think about it, there's no reason for GHC to not use some advanced algorithm for multiplication since they already supported it out of the box.

The last time I checked, GMP is blazing fast and even when used in the normal double range, is at least as fast as gcc's compilation result.

There's a proposal on removing GMP from GHC, but it seems rather inactive.

EDIT: Thanks to @danvari, here are the different algorithms GMP uses: http://gmplib.org/manual/Multiplication-Algorithms.html#Multiplication-Algorithms. It seems Karatsuba does get used when the numbers are small enough, and aside from the usual Toom-Cook family, FFT is also used.