Minimal-operation shift-and-add (or subtract)

If you mean 4 through 7 in a literal sense, that is scaling by those four 
numbers, 4 requires 2 shifts, 5 2 shifts and an add, 6 2 shifts and an add 
and seven needs 3 shifts and a subtract.

Hul

Tim Wescott <seemywebsite@myfooter.really> wrote:
> On Thu, 01 Sep 2016 18:40:25 -0400, rickman wrote:

> > On 9/1/2016 4:24 PM, Tim Wescott wrote:
> >> On Thu, 01 Sep 2016 13:19:09 -0700, lasselangwadtchristensen wrote:
> >>
> >>> Den torsdag den 1. september 2016 kl. 21.53.33 UTC+2 skrev Tim
> >>> Wescott:
> >>>> There's a method that I know, but can't remember the name.  And now I
> >>>> want to tell someone to Google for it.
> >>>>
> >>>> It basically starts with the notion of multiplying by shift-and-add,
> >>>> but uses the fact that if you shift and then either add or subtract,
> >>>> you can minimize "addition" operations.
> >>>>
> >>>> I.e., 255 = 256 - 1, 244 = 256 - 16 + 4, etc.
> >>>>
> >>>>
> >>> Booth?
> >>>
> >>> -Lasse
> >>
> >> That's it.  Thanks.
> > 
> > That is very familiar from college, but I don't recall the utility.  It
> > would be useful for multiplying by constants, but otherwise how would
> > this be used to advantage?  It would save add/subtract operations, but I
> > can't think of another situation where this would be useful.
> > 
> > If the algorithm is doing an add and shift, the add does not increase
> > the time or the hardware.  If building the full multiplier, an adder is
> > included for each stage, it is either used or not used.  When done in
> > software, the same applies.  It is easier to do the add than to skip
> > over it.

> I asked here and on comp.arch.embedded.  It's for a guy who's doing 
> assembly-language programming on a PIC12xxx -- for that guy, and for a 
> small range of constants (4 through 7), it can save time over a full-
> blown multiplication algorithm.

> -- 

> Tim Wescott
> Wescott Design Services
> http://www.wescottdesign.com

> I'm looking for work -- see my website!