Booth does two bits per clock cycle:

(* 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

(C) 2008-10, DJ Greaves, University of Cambridge, Computer Laboratory.