current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
stack overflow careers
Sign up ×
Stack Overflow is a community of 4.7 million programmers, just like you, helping each other. Join them, it only takes a minute:
up vote 3 down vote favorite
1

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?

share|improve this question
1  
This base =10^((length . show $ max x y) div` 2)` is not good. Although GHC's Show instance for Integer is orders of magnitude faster than Java's BigInteger.toString() or Python's str for large numbers, that is still fairly slow (think about what it has to do). You should get a nice speedup using GHC.Float.integerLogBase there. Still better if you used a power-of-2 base, probably. – Daniel Fischer Jun 8 '13 at 5:12

1 Answer 1

up vote 8 down vote accepted

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.

share|improve this answer
    
Thank you for your answer. I see. In that case, my algorithm is not too bad, and it is just * is really fast? – Tengu Jun 7 '13 at 17:47
    
Could be the case, at least that is my idea. I used GMP several years ago, and find it to be amazing. It seems there are a lot of algorithms there are rather cutting edge research ideas, so I wouldn't expect it to be surpassed easily. – Ziyao Wei Jun 7 '13 at 17:48
1  
I see. Well, it was a good practice to implement algorithm. Thank you for your answer. – Tengu Jun 7 '13 at 17:56
1  
GMP uses the following algorithms for integer multiplication (ordered by the size of the input numbers): 1. The naive (schoolbook) algorithm, 2. Karatsuba, 3. Toom 3-Way, 4. Toom 4-Way, 5. Higher degree Toom'n'Half, 6. Fast Fourier Transform multiplication. – dnaq Jun 7 '13 at 20:13
1  
gmplib.org/manual/… – dnaq Jun 7 '13 at 20:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.