EDAboard.com | EDAboard.eu | EDAboard.de | EDAboard.co.uk | RTV forum PL | NewsGroups PL

elektroda.net NewsGroups Forum Index - FPGA - **Minimal-operation shift-and-add (or subtract)**

Guest

Fri Sep 02, 2016 1:53 am

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

Guest

Fri Sep 02, 2016 1:53 am

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.

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

Guest

Fri Sep 02, 2016 1:53 am

Den fredag den 2. september 2016 kl. 00.40.28 UTC+2 skrev rickman:

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.

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.

you only need half the stages so it is half the size* and the critical path through your adders are only half as long

* you need a few multiplexors to choose between x1 and x2, subtract is invert and carry in

-Lasse

Guest

Fri Sep 02, 2016 1:53 am

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.

Canonical Signed Digit (CSD) representation. The CSD form of any number has at least 1/3 of the bits cleared.

244 = 011110100 = +000-0100

(Replace 01111 with +000-)

Guest

Fri Sep 02, 2016 1:53 am

Canonical Signed Digit (CSD) representation. The CSD form of any number has at least 1/3 of the bits cleared.

244 = 011110100 = +000-0100

(Replace 01111 with +000-)

I meant:

244 = 011110100 = +000-0+00

Guest

Fri Sep 02, 2016 2:24 am

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

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.

--

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

Guest

Fri Sep 02, 2016 4:40 am

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.

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.

--

Rick C

Guest

Fri Sep 02, 2016 5:09 am

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.

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!

Guest

Fri Sep 02, 2016 7:30 am

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

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.

Oh, sure, I use that all the time for constant multiplication. No magic

involved. In some cases (such at multiplying by 4) it is simpler to

just use a simple shift and add (which becomes trivial for a single

bit). Even for multipliers with two bits set, it is easier to use a

simple add the shifted values. In fact, the only case of multiplying by

numbers in the range of 4 to 7 where Booth's algorithm simplifies the

work is 7. Since there are only four cases, I expect this could easily

be implemented as four special cases.

--

Rick C

Guest

Fri Sep 02, 2016 12:39 pm

On 9/1/2016 7:22 PM, lasselangwadtchristensen_at_gmail.com wrote:

Den fredag den 2. september 2016 kl. 00.40.28 UTC+2 skrev rickman:

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.

you only need half the stages so it is half the size* and the

critical path through your adders are only half as long

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.

you only need half the stages so it is half the size* and the

critical path through your adders are only half as long

I think you need to look at the algorithm again. The degenerate case is

a multiplier with alternating ones and zeros. An add or subtract is

needed at each 1->0 or 0->1 transition. Since every bit is a transition

you still need an adder/subtractor for every bit.

Of course you could add logic to detect these cases and do fewer adder

ops, but then that is not Booth's algorithm anymore and is much more

complex. Booth's algorithm looks at pairs of bits in the multiplier,

this would require looking at more bits.

If you are thinking in terms of constant multiplication then again, this

is a modified method that combines Booth's with straight adds.

* you need a few multiplexors to choose between x1 and x2, subtract

is invert and carry in

is invert and carry in

Multiplexers are not low cost in any sense in many technologies, but it

doesn't matter. Booth's algorithm doesn't use multiplexers.

--

Rick C

Guest

Fri Sep 02, 2016 4:59 pm

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.

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

Guest

Fri Sep 02, 2016 10:01 pm

Den fredag den 2. september 2016 kl. 08.39.20 UTC+2 skrev rickman:

On 9/1/2016 7:22 PM, lasselangwadtchristensen_at_gmail.com wrote:

Den fredag den 2. september 2016 kl. 00.40.28 UTC+2 skrev rickman:

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.

you only need half the stages so it is half the size* and the

critical path through your adders are only half as long

I think you need to look at the algorithm again. The degenerate case is

a multiplier with alternating ones and zeros. An add or subtract is

needed at each 1->0 or 0->1 transition. Since every bit is a transition

you still need an adder/subtractor for every bit.

Of course you could add logic to detect these cases and do fewer adder

ops, but then that is not Booth's algorithm anymore and is much more

complex. Booth's algorithm looks at pairs of bits in the multiplier,

this would require looking at more bits.

Den fredag den 2. september 2016 kl. 00.40.28 UTC+2 skrev rickman:

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.

you only need half the stages so it is half the size* and the

critical path through your adders are only half as long

I think you need to look at the algorithm again. The degenerate case is

a multiplier with alternating ones and zeros. An add or subtract is

needed at each 1->0 or 0->1 transition. Since every bit is a transition

you still need an adder/subtractor for every bit.

Of course you could add logic to detect these cases and do fewer adder

ops, but then that is not Booth's algorithm anymore and is much more

complex. Booth's algorithm looks at pairs of bits in the multiplier,

this would require looking at more bits.

you are right, I was thinking of "modified Booth" it looks at 3 bits at

a time,

http://www.ellab.physics.upatras.gr/~bakalis/Eudoxus/mbm8.gif

If you are thinking in terms of constant multiplication then again, this

is a modified method that combines Booth's with straight adds.

* you need a few multiplexors to choose between x1 and x2, subtract

is invert and carry in

Multiplexers are not low cost in any sense in many technologies, but it

doesn't matter. Booth's algorithm doesn't use multiplexers.

is a modified method that combines Booth's with straight adds.

* you need a few multiplexors to choose between x1 and x2, subtract

is invert and carry in

Multiplexers are not low cost in any sense in many technologies, but it

doesn't matter. Booth's algorithm doesn't use multiplexers.

may not be low cost, but compared to a full adder?

and since the inputs come from the multiplicand and the multiplier not from other intermediate results it shouldn't be in the critical path

-Lasse

Guest

Sat Sep 03, 2016 2:08 am

Den lørdag den 3. september 2016 kl. 01.37.56 UTC+2 skrev rickman:

On 9/2/2016 4:01 PM, lasselangwadtchristensen_at_gmail.com wrote:

Den fredag den 2. september 2016 kl. 08.39.20 UTC+2 skrev rickman:

On 9/1/2016 7:22 PM, lasselangwadtchristensen_at_gmail.com wrote:

Den fredag den 2. september 2016 kl. 00.40.28 UTC+2 skrev

rickman:

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.

you only need half the stages so it is half the size* and the

critical path through your adders are only half as long

I think you need to look at the algorithm again. The degenerate

case is a multiplier with alternating ones and zeros. An add or

subtract is needed at each 1->0 or 0->1 transition. Since every

bit is a transition you still need an adder/subtractor for every

bit.

Of course you could add logic to detect these cases and do fewer

adder ops, but then that is not Booth's algorithm anymore and is

much more complex. Booth's algorithm looks at pairs of bits in the

multiplier, this would require looking at more bits.

you are right, I was thinking of "modified Booth" it looks at 3 bits

at a time,

http://www.ellab.physics.upatras.gr/~bakalis/Eudoxus/mbm8.gif

If you are thinking in terms of constant multiplication then again,

this is a modified method that combines Booth's with straight

adds.

* you need a few multiplexors to choose between x1 and x2,

subtract is invert and carry in

Multiplexers are not low cost in any sense in many technologies,

but it doesn't matter. Booth's algorithm doesn't use

multiplexers.

may not be low cost, but compared to a full adder?

In an FPGA the unit of size is the Logic Cell (LC), a LUT and a FF.

Because there is extra carry logic in the LC one bit of an adder is the

same logic as one bit of a multiplexer. The only disadvantage of an

adder is the carry propagation time, but they don't cascade, properly

designed you end up with one ripple cascade through one adder and then

the other logic delays as the adders all cascade in parallel.

Den fredag den 2. september 2016 kl. 08.39.20 UTC+2 skrev rickman:

On 9/1/2016 7:22 PM, lasselangwadtchristensen_at_gmail.com wrote:

Den fredag den 2. september 2016 kl. 00.40.28 UTC+2 skrev

rickman:

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.

you only need half the stages so it is half the size* and the

critical path through your adders are only half as long

I think you need to look at the algorithm again. The degenerate

case is a multiplier with alternating ones and zeros. An add or

subtract is needed at each 1->0 or 0->1 transition. Since every

bit is a transition you still need an adder/subtractor for every

bit.

Of course you could add logic to detect these cases and do fewer

adder ops, but then that is not Booth's algorithm anymore and is

much more complex. Booth's algorithm looks at pairs of bits in the

multiplier, this would require looking at more bits.

you are right, I was thinking of "modified Booth" it looks at 3 bits

at a time,

http://www.ellab.physics.upatras.gr/~bakalis/Eudoxus/mbm8.gif

If you are thinking in terms of constant multiplication then again,

this is a modified method that combines Booth's with straight

adds.

* you need a few multiplexors to choose between x1 and x2,

subtract is invert and carry in

Multiplexers are not low cost in any sense in many technologies,

but it doesn't matter. Booth's algorithm doesn't use

multiplexers.

may not be low cost, but compared to a full adder?

In an FPGA the unit of size is the Logic Cell (LC), a LUT and a FF.

Because there is extra carry logic in the LC one bit of an adder is the

same logic as one bit of a multiplexer. The only disadvantage of an

adder is the carry propagation time, but they don't cascade, properly

designed you end up with one ripple cascade through one adder and then

the other logic delays as the adders all cascade in parallel.

sure most fpgas have fast carry chains or build in multipliers so hand

coding "fancy" multiplier structures might not come out ahead

and since the inputs come from the multiplicand and the multiplier

not from other intermediate results it shouldn't be in the critical

path

???

I don't see how you use multiplexers instead of adders. If the

multiplier changes from one calculation to the next you need adders in

every position. If the multiplier is fixed the combinations of sums is

fixed and no multiplexers are needed.

with a regular multiplier you have to go through N layers of adders

with a modified Booth you only have to go through N/2 adders

-Lasse

Guest

Sat Sep 03, 2016 5:37 am

On 9/2/2016 4:01 PM, lasselangwadtchristensen_at_gmail.com wrote:

Den fredag den 2. september 2016 kl. 08.39.20 UTC+2 skrev rickman:

On 9/1/2016 7:22 PM, lasselangwadtchristensen_at_gmail.com wrote:

Den fredag den 2. september 2016 kl. 00.40.28 UTC+2 skrev

rickman:

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.

you only need half the stages so it is half the size* and the

critical path through your adders are only half as long

I think you need to look at the algorithm again. The degenerate

case is a multiplier with alternating ones and zeros. An add or

subtract is needed at each 1->0 or 0->1 transition. Since every

bit is a transition you still need an adder/subtractor for every

bit.

Of course you could add logic to detect these cases and do fewer

adder ops, but then that is not Booth's algorithm anymore and is

much more complex. Booth's algorithm looks at pairs of bits in the

multiplier, this would require looking at more bits.

you are right, I was thinking of "modified Booth" it looks at 3 bits

at a time,

http://www.ellab.physics.upatras.gr/~bakalis/Eudoxus/mbm8.gif

If you are thinking in terms of constant multiplication then again,

this is a modified method that combines Booth's with straight

adds.

* you need a few multiplexors to choose between x1 and x2,

subtract is invert and carry in

Multiplexers are not low cost in any sense in many technologies,

but it doesn't matter. Booth's algorithm doesn't use

multiplexers.

may not be low cost, but compared to a full adder?

On 9/1/2016 7:22 PM, lasselangwadtchristensen_at_gmail.com wrote:

Den fredag den 2. september 2016 kl. 00.40.28 UTC+2 skrev

rickman:

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.

you only need half the stages so it is half the size* and the

critical path through your adders are only half as long

I think you need to look at the algorithm again. The degenerate

case is a multiplier with alternating ones and zeros. An add or

subtract is needed at each 1->0 or 0->1 transition. Since every

bit is a transition you still need an adder/subtractor for every

bit.

Of course you could add logic to detect these cases and do fewer

adder ops, but then that is not Booth's algorithm anymore and is

much more complex. Booth's algorithm looks at pairs of bits in the

multiplier, this would require looking at more bits.

you are right, I was thinking of "modified Booth" it looks at 3 bits

at a time,

http://www.ellab.physics.upatras.gr/~bakalis/Eudoxus/mbm8.gif

If you are thinking in terms of constant multiplication then again,

this is a modified method that combines Booth's with straight

adds.

* you need a few multiplexors to choose between x1 and x2,

subtract is invert and carry in

Multiplexers are not low cost in any sense in many technologies,

but it doesn't matter. Booth's algorithm doesn't use

multiplexers.

may not be low cost, but compared to a full adder?

In an FPGA the unit of size is the Logic Cell (LC), a LUT and a FF.

Because there is extra carry logic in the LC one bit of an adder is the

same logic as one bit of a multiplexer. The only disadvantage of an

adder is the carry propagation time, but they don't cascade, properly

designed you end up with one ripple cascade through one adder and then

the other logic delays as the adders all cascade in parallel.

and since the inputs come from the multiplicand and the multiplier

not from other intermediate results it shouldn't be in the critical

path

not from other intermediate results it shouldn't be in the critical

path

???

I don't see how you use multiplexers instead of adders. If the

multiplier changes from one calculation to the next you need adders in

every position. If the multiplier is fixed the combinations of sums is

fixed and no multiplexers are needed.

--

Rick C

Guest

Sat Sep 03, 2016 7:30 am

On 9/2/2016 8:08 PM, lasselangwadtchristensen_at_gmail.com wrote:

Den lørdag den 3. september 2016 kl. 01.37.56 UTC+2 skrev rickman:

On 9/2/2016 4:01 PM, lasselangwadtchristensen_at_gmail.com wrote:

Den fredag den 2. september 2016 kl. 08.39.20 UTC+2 skrev rickman:

On 9/1/2016 7:22 PM, lasselangwadtchristensen_at_gmail.com wrote:

Den fredag den 2. september 2016 kl. 00.40.28 UTC+2 skrev

rickman:

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.

you only need half the stages so it is half the size* and the

critical path through your adders are only half as long

I think you need to look at the algorithm again. The degenerate

case is a multiplier with alternating ones and zeros. An add or

subtract is needed at each 1->0 or 0->1 transition. Since every

bit is a transition you still need an adder/subtractor for every

bit.

Of course you could add logic to detect these cases and do fewer

adder ops, but then that is not Booth's algorithm anymore and is

much more complex. Booth's algorithm looks at pairs of bits in the

multiplier, this would require looking at more bits.

you are right, I was thinking of "modified Booth" it looks at 3 bits

at a time,

http://www.ellab.physics.upatras.gr/~bakalis/Eudoxus/mbm8.gif

If you are thinking in terms of constant multiplication then again,

this is a modified method that combines Booth's with straight

adds.

* you need a few multiplexors to choose between x1 and x2,

subtract is invert and carry in

Multiplexers are not low cost in any sense in many technologies,

but it doesn't matter. Booth's algorithm doesn't use

multiplexers.

may not be low cost, but compared to a full adder?

In an FPGA the unit of size is the Logic Cell (LC), a LUT and a FF.

Because there is extra carry logic in the LC one bit of an adder is the

same logic as one bit of a multiplexer. The only disadvantage of an

adder is the carry propagation time, but they don't cascade, properly

designed you end up with one ripple cascade through one adder and then

the other logic delays as the adders all cascade in parallel.

sure most fpgas have fast carry chains or build in multipliers so hand

coding "fancy" multiplier structures might not come out ahead

and since the inputs come from the multiplicand and the multiplier

not from other intermediate results it shouldn't be in the critical

path

???

I don't see how you use multiplexers instead of adders. If the

multiplier changes from one calculation to the next you need adders in

every position. If the multiplier is fixed the combinations of sums is

fixed and no multiplexers are needed.

with a regular multiplier you have to go through N layers of adders

with a modified Booth you only have to go through N/2 adders

On 9/2/2016 4:01 PM, lasselangwadtchristensen_at_gmail.com wrote:

Den fredag den 2. september 2016 kl. 08.39.20 UTC+2 skrev rickman:

On 9/1/2016 7:22 PM, lasselangwadtchristensen_at_gmail.com wrote:

Den fredag den 2. september 2016 kl. 00.40.28 UTC+2 skrev

rickman:

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.

you only need half the stages so it is half the size* and the

critical path through your adders are only half as long

I think you need to look at the algorithm again. The degenerate

case is a multiplier with alternating ones and zeros. An add or

subtract is needed at each 1->0 or 0->1 transition. Since every

bit is a transition you still need an adder/subtractor for every

bit.

Of course you could add logic to detect these cases and do fewer

adder ops, but then that is not Booth's algorithm anymore and is

much more complex. Booth's algorithm looks at pairs of bits in the

multiplier, this would require looking at more bits.

you are right, I was thinking of "modified Booth" it looks at 3 bits

at a time,

http://www.ellab.physics.upatras.gr/~bakalis/Eudoxus/mbm8.gif

If you are thinking in terms of constant multiplication then again,

this is a modified method that combines Booth's with straight

adds.

* you need a few multiplexors to choose between x1 and x2,

subtract is invert and carry in

Multiplexers are not low cost in any sense in many technologies,

but it doesn't matter. Booth's algorithm doesn't use

multiplexers.

may not be low cost, but compared to a full adder?

In an FPGA the unit of size is the Logic Cell (LC), a LUT and a FF.

Because there is extra carry logic in the LC one bit of an adder is the

same logic as one bit of a multiplexer. The only disadvantage of an

adder is the carry propagation time, but they don't cascade, properly

designed you end up with one ripple cascade through one adder and then

the other logic delays as the adders all cascade in parallel.

sure most fpgas have fast carry chains or build in multipliers so hand

coding "fancy" multiplier structures might not come out ahead

and since the inputs come from the multiplicand and the multiplier

not from other intermediate results it shouldn't be in the critical

path

???

I don't see how you use multiplexers instead of adders. If the

multiplier changes from one calculation to the next you need adders in

every position. If the multiplier is fixed the combinations of sums is

fixed and no multiplexers are needed.

with a regular multiplier you have to go through N layers of adders

with a modified Booth you only have to go through N/2 adders

and N/2 multiplexers which have the same delay... PLUS the selectable

inverter which may or may not be combined with the adder. What's the

point? A simple adder has N stages of delay in an FPGA, same as the

much more complicated modified Booth's adder. In an ASIC there may be

some advantage. In software, I expect the much more complicated control

will make the modified Booth's algorithm the slowest of the three.

People so often forget that multiplexers are not trivial logic.

--

Rick C

elektroda.net NewsGroups Forum Index - FPGA - **Minimal-operation shift-and-add (or subtract)**