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. *)