# Re: multiplication by constant - quick comparison of algorithms

## joe@babel.ho.att.com (Joseph M Orost)Wed, 28 Oct 1992 13:43:48 GMT

From comp.compilers

Related articles
multiplication by constant - quick comparison of algorithms wu@sequent.com (Youfeng Wu) (1992-10-21)
Re: multiplication by constant - quick comparison of algorithms preston@helena.cs.rice.edu (1992-10-21)
Re: multiplication by constant - quick comparison of algorithms bgb@iexist.att.com (1992-10-25)
Re: multiplication by constant - quick comparison of algorithms chased@rbbb.Eng.Sun.COM (1992-10-27)
Re: multiplication by constant - quick comparison of algorithms joe@babel.ho.att.com (1992-10-28)
| List of all articles for this month |

 Newsgroups: comp.compilers From: joe@babel.ho.att.com (Joseph M Orost) Organization: Echo Logic Date: Wed, 28 Oct 1992 13:43:48 GMT Summary: Shift & Subtract is fine References: 92-10-079 92-10-095 Keywords: arithmetic, optimize

bgb@iexist.att.com (Brian G Beuning) writes:
>Isn't it a little dangerous to use sub? Won't it overflow sometimes when
>the multiply would not.

As long as the target machine supports non-overflow faulting logical shift
left and non-faulting subtract, the shift & subtract trick works fine.
The "overflow" does not prevent the correct answer from being obtained.

e.g. x * 7 = (x << 3) - x

For a large input, say 0x12492492:

(0x7ffffffe) = ((0x92492490) - 0x12492492)

On some machines, the operations in question are called "unsigned".
(e.g., subu).

If you need to fully mimic the potential faulting of the multiply
instruction (e.g. for compiling Ada), then the shift and subtract
technique cannot be used. However, multiple adds can still be used (and
even shifts if the target machine supports an overflow-checking arithmetic
left shift).

regards,
joe

--
Full Name: Joseph M. Orost
EMail: joe@babel.ho.att.com
Organization: Echo Logic
SurfaceMail: 943 Holmdel Rd.; Cruz Plaza; Holmdel, NJ 07733
Phone: +1 (908) 946-1115
--

Post a followup to this message