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