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

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.

-- 
Tim Wescott
Control systems, embedded software and circuit design
I'm looking for work!  See my website if you're interested
http://www.wescottdesign.com

On 9/1/2016 12:53 PM, Tim Wescott wrote:
> 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.

Unsure of your desired goal, here.

If you are trying to implement multiplication and define
"work" as an addition operation (i.e., 0x7F * N has more
"work" than 0x01 * N), then Booth's algorithm is more
economical -- for *certain* multipliers (e.g., 0x3C * N
will do less work than 0x55 * N under Booth but will do
the same amount of "work" under the classic shift-and-add).

E.g., the 25LS14.

On 1.9.16 22:53, Tim Wescott wrote:
> 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.


It seems that you're after Booth's algorithm:
<https://en.wikipedia.org/wiki/Booth%27s_multiplication_algorithm>.

-- 

-TV

On Fri, 02 Sep 2016 13:59:30 +0300, Tauno Voipio wrote:

> On 1.9.16 22:53, Tim Wescott wrote:
>> 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.
> 
> 
> It seems that you're after Booth's algorithm:
> <https://en.wikipedia.org/wiki/Booth%27s_multiplication_algorithm>.

Yes.  Got an answer on the fpga group, and didn't say so here.

Thanks.

-- 
Tim Wescott
Control systems, embedded software and circuit design
I'm looking for work!  See my website if you're interested
http://www.wescottdesign.com