When is Karatsuba faster?

multiplication.hs

import Data.List

{-

We are assumming the multiplication is happening in decimal digits. Here is the yardstick with which we are measuring the number of operations

1. Every single digit multiplication is 1 step
2. Adding two n-digit numbers is n steps.
   Adding an m-digit and an n-digit number takes max(m, n) steps.
   Adding two n-digit numbers produce an (n+1)-digit number.
   Adding three or more numbers is done by adding them one by one.
3. Multiplying an m-digit number by 10^n takes (m + n) steps.

-}

addition n = n

naive n =
  n*n                                  -- n^2 lookups for the multiplication tables
  + (((n+1)+(2*n - 1))*(n-1)) `div` 2  -- now that you have produced n lines
                                       --, you need to add them up

seminaive n =
  4 * naive(n `div` 2)                 -- 4 naive multiplications
  + 2 * n + 3 * (n `div` 2)            -- cost of multiplying by 10^n and 10^(n/2)
  + 2*n + ((2*n)+1)                    -- cost of final addition

semikaratsuba n =
  2 * naive(n `div` 2)                      -- 2 usual naive multiplications
  + n + naive((n `div` 2) + 1) + n + (n+1)  -- cost of the Karatsuba step
  + 2 * n + 3 * (n `div` 2)                 -- cost of the shifts
  + 2*n + (2*n+1)                           -- cost of the final addition

comparePerformance n = intercalate "\t\t\t" $ map show [n, naive n, seminaive n, semikaratsuba n]

comparePerformances m n = intercalate "\n" $ map comparePerformance (filter even [m .. n])

-- The resulting program compares the performance of the three algorithms for 1 to 40 digit numbers.
-- We ignore the odd numbers because they complicate the calculation
-- First column is the number of digits, second, third and fourth columns are the naive, seminaive and semikaratsuba algorithms respectively
main = putStrLn $ comparePerformances 1 40

{-

The output of this program looks like this:

2			7			20			32
4			34			59			76
6			81			118			135
8			148			197			209
10			235			296			298
12			342			415			402
14			469			554			521
16			616			713			655
18			783			892			804
20			970			1091			968
22			1177			1310			1147
24			1404			1549			1341
26			1651			1808			1550
28			1918			2087			1774
30			2205			2386			2013
32			2512			2705			2267
34			2839			3044			2536
36			3186			3403			2820
38			3553			3782			3119
40			3940			4181			3433


Notice that the semikaratsuba algorithm performs better only after about 20 digits.

-}