1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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