# 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)

add :: Bits -> Bits -> Bits

-- 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?

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