Is there any bitwise multiplication algorithm that is sub O(n^2)?

The following program implements a simple algorithm for binary multiplication:

-- Numbers as infinite streams of bits, least significant bits first
data Bits
= O Bits
| I Bits

-- Increments a number
suc :: Bits -> Bits
suc (O xs) = I xs
suc (I xs) = O (suc xs)

-- Adds two numbers
add :: Bits -> Bits -> Bits
add (O xs) (O ys) =      (O (add xs ys))
add (O xs) (I ys) =      (I (add xs ys))
add (I xs) (O ys) =      (I (add xs ys))
add (I xs) (I ys) = (suc (I (add xs ys)))

-- Multiplies two numbers
mul :: Bits -> Bits -> Bits
mul (O xs) ys =        (O (mul xs ys))
mul (I xs) ys = add ys (O (mul xs ys))


(The complete program can be seen here.)

This algorithm, although simple, has O(N^2) complexity. Are there similarly simple algorithms with lower complexities?

1 Answer

Is Karatsuba algorithm simple enough? It's complexity is $O(n^{1.59})$.

• I wasn't aware it applies to binary representations (i.e., no built-in 32-bit mul). – MaiaVictor Mar 29 '18 at 3:09
• @MaiaVictor you can split the operands recursively until the algorithm would be more expensive than the naive one after which you go back to naive. – ratchet freak Mar 29 '18 at 11:11