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

[Hul Tytus]

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!