Path: utzoo!mnetor!uunet!lll-winken!lll-tis!ames!ptsfa!pacbell!att-ih!inuxc!iuvax!pur-ee!hankd
From: hankd@pur-ee.UUCP (Hank Dietz)
Newsgroups: comp.arch
Subject: Re: Shift and Subtract is NOT Multiply
Message-ID: <7662@pur-ee.UUCP>
Date: 2 Mar 88 05:05:13 GMT
References: <7649@pur-ee.UUCP> <7276@sol.ARPA>
Organization: Purdue University Engineering Computer Network
Lines: 26
Summary: It is if you watch precision/bounds

In article <7276@sol.ARPA>, crowl@cs.rochester.edu (Lawrence Crowl) writes:
> In article <7649@pur-ee.UUCP> hankd@pur-ee.UUCP (Hank Dietz) writes:
> >For example, a multiply by 7 (not a nice power of 2) is really shift to
> >multiply by 8 and then subtract the original number.
> 
> If you use this method for multiplication by 7, and you do not provide for
> a double width result, using subtraction will lose the overflow information.
> For example, a*7 implemented as (a<<3)-a may overflow where (a<<2)+(a<<1)+a
> will not.  If we detect an overflow with (a<<3)-a, then we cannot immediately
> tell whether or not a*7 would overflow.

I suggested this for multiplies in computing offsets given an
array subscript.  In such cases, the compiler can trivially
know whether a range error could occur since it knows the
possible range of values for the subscript and hence it also
knows the range of result values from the multiply.  I thought
this condition was obvious enough that it didn't need to be
stated explicitly...  I guess I was wrong.  Anyway, even for
an arbitrary value being multiplied by a constant, the same
range information can usually be obtained by fairly simple
compile-time analysis.  In short, if it MIGHT overflow, then
you use only shifts and adds; otherwise, subs are ok too.
Even violating that rule, "a double width result" is overkill;
in the example of multiply by 8 and subtract original value,
you'd need at most one extra bit of precision (e.g., carry).

					-hankd