Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!rochester!crowl
From: crowl@rochester.ARPA (Lawrence Crowl)
Newsgroups: comp.arch
Subject: Multiply as Shift-Add(Subtract)
Message-ID: <27685@rochester.ARPA>
Date: Tue, 12-May-87 12:21:13 EDT
Article-I.D.: rocheste.27685
Posted: Tue May 12 12:21:13 1987
Date-Received: Fri, 15-May-87 00:46:41 EDT
References: <1270@aw.sei.cmu.edu> <8012@utzoo.UUCP> <16640@amdcad.AMD.COM> <381@dumbo.UUCP>
Reply-To: crowl@rochester.UUCP (Lawrence Crowl)
Organization: U of Rochester, CS Dept, Rochester, NY
Lines: 39

Standard architectures provide a multiply instruction so that "i * 57"
compiles to a single, general purpose multiply instruction.

The AMD machine provides a decomposed multiply instruction that must
be executed n times in sequence for an n bit multiply.  In article
<16640@amdcad.AMD.COM>, tim@amdcad.AMD.COM (Tim Olson) notes that
"bits(57) == 6".  Using "#" to represent the decomposed multiply
instruction, "i * 57" is translated to:

    ((((((i # 57) # 57) # 57) # 57) # 57) # 57) # 57

In article <16640@amdcad.AMD.COM>, tim@amdcad.AMD.COM (Tim Olson) also
notes that "57 == 32 + 16 + 8 + 1" so that the multiply can be more 
efficiently translated to:

    (i << 5) + (i << 4) + (i << 3) + i 

In article <381@dumbo.UUCP> hansen@mips.UUCP (Craig Hansen) further
notes that "57 == (8 - 1) * 8 + 1".  Using this the muliply is yet
more efficiently translated to: 

    (((i << 3) - i) << 3) + i

Now a problem arises.  In the first three approaches an overflow at
any step indicates an overflow for the entire multiply.  However, in
the last approach, an overflow may occur at a step in the computation 
while the entire multiply itself does not overflow.  For example, 
assume a sixteen bit two's complement integer.  The multiplication
"i * 63" where i == 520 is not an overflow (520 * 63 == 32760).  The
expression translated to the shift-subtract approach is "(i << 6) - i".
The shift step overflows because "520 << 6" is greater than 32767.

Finally, the question: how do implementations using subtracts in the
shift-add approach to multiplication detect overflow for an entire
multiplication?
-- 
  Lawrence Crowl		716-275-5766	University of Rochester
			crowl@rochester.arpa	Computer Science Department
 ...!{allegra,decvax,seismo}!rochester!crowl	Rochester, New York,  14627