CBG SQUANDERER BOOTH EXAMPLE.
(* Call this function with c=0 and carry=0 to multiply x by y. *)
fun booth(x, y, c, carry) =
if(x=0 andalso carry=0) then c else
let val x' = x div 4
val y' = y * 4
val n = (x mod 4) + carry
val (carry', c') = case (n) of
(0) => (0, c)
|(1) => (0, c+y)
|(2) => (0, c+2*y)
|(3) => (1, c-y)
|(4) => (1, c)
in booth(x', y', c', carry')
end
;
(* Booth's multiplier is twice as fast as binary long multiplication
but still only uses a single adder. The trick is that the adder is
sometimes used as a subtractor, using the identity 3=4-1. The
multiplication and division and modulus by powers of 2 are all
performed with wiring and so require no gates to perform. (The
fixed-width addition of the carry to form n is considered part of the
control logic, rather than counting as a datapath adder.)
(C) DJG 1995.
*)