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 1


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

  • $\begingroup$ I wasn't aware it applies to binary representations (i.e., no built-in 32-bit mul). $\endgroup$
    – MaiaVictor
    Mar 29, 2018 at 3:09
  • 1
    $\begingroup$ @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. $\endgroup$ Mar 29, 2018 at 11:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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