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?