sicp 1.18

sicp-1.18.hs

-- [Design an *iterative* process for multiplying to integers that] uses a
-- logarithmic number of steps.

double :: Integer -> Integer
double x = x + x

halve :: Integer -> Integer
halve x = x `div` 2

multiply :: Integer -> Integer -> Integer
multiply x y = multiply' 0 x y

multiply' :: Integer -> Integer -> Integer -> Integer
multiply' state x y
    | y == 0 = state
    | odd y = multiply' (state + x) x (y - 1)
    | otherwise = multiply' (state + x * halve y) x (halve y)