const multiplication using shift and add solve

[Yang Luo]

eg1:
c=a*29;-->c=a*32-a*4+a-->c=a<<5-a<<2+a;
eg2:
c=a*72;-->c=a*8*(8+1)-->c=(a<<3)<<3+a<<3;
some papers researched this topic, but I didn't find any tools/codes to do this.
Is there anybody used this way to optimazation const multiplication?

 

[Allan Herriman]

On Fri, 26 Feb 2016 00:43:45 -0800, Yang Luo wrote:

eg1:
c=a*29;-->c=a*32-a*4+a-->c=a<<5-a<<2+a;
eg2:
c=a*72;-->c=a*8*(8+1)-->c=(a<<3)<<3+a<<3;
some papers researched this topic, but I didn't find any tools/codes to
do this.
Is there anybody used this way to optimazation const multiplication?

The first step, e.g. c=a*29;-->c=a*32-a*4+a seems similar to Booth's
algorithm.

https://en.wikipedia.org/wiki/Booth's_multiplication_algorithm

Allan

 

[rickman]

On 2/26/2016 10:17 AM, Allan Herriman wrote:

On Fri, 26 Feb 2016 00:43:45 -0800, Yang Luo wrote:

eg1:
c=a*29;-->c=a*32-a*4+a-->c=a<<5-a<<2+a;
eg2:
c=a*72;-->c=a*8*(8+1)-->c=(a<<3)<<3+a<<3;
some papers researched this topic, but I didn't find any tools/codes to
do this.
Is there anybody used this way to optimazation const multiplication?


The first step, e.g. c=a*29;-->c=a*32-a*4+a seems similar to Booth's
algorithm.

https://en.wikipedia.org/wiki/Booth's_multiplication_algorithm

The other example eg2 shows a multiplication by 72 which is 64+8. I'm
not sure what the alternate form is doing any different from multiplying
by 64 and 8 and adding those results. Left shift by 3 twice is the same
as a left shift by 6 which is the same as multiplying by 64.

Why would a paper be needed to understand either of these examples?
Multiplying by constants is well understood.

--

Rick

 

[Yang Luo]

在 2016年2月28日星期日 UTC+8上午1:32:40，rickman写道：

On 2/26/2016 10:17 AM, Allan Herriman wrote:
On Fri, 26 Feb 2016 00:43:45 -0800, Yang Luo wrote:

eg1:
c=a*29;-->c=a*32-a*4+a-->c=a<<5-a<<2+a;
eg2:
c=a*72;-->c=a*8*(8+1)-->c=(a<<3)<<3+a<<3;
some papers researched this topic, but I didn't find any tools/codes to
do this.
Is there anybody used this way to optimazation const multiplication?


The first step, e.g. c=a*29;-->c=a*32-a*4+a seems similar to Booth's
algorithm.

https://en.wikipedia.org/wiki/Booth's_multiplication_algorithm

The other example eg2 shows a multiplication by 72 which is 64+8. I'm
not sure what the alternate form is doing any different from multiplying
by 64 and 8 and adding those results. Left shift by 3 twice is the same
as a left shift by 6 which is the same as multiplying by 64.
Yes. Above is only an example, not the optimale results. I want to find a tool to realize it quickly. Here I find a tool url:
https://github.com/nkkav/kmul

Why would a paper be needed to understand either of these examples?
Multiplying by constants is well understood.
In FPGA, multiplying will cost much area, in this way, can avoid a multiplier.
--

Rick

 

[Allan Herriman]

On Sat, 27 Feb 2016 12:32:36 -0500, rickman wrote:

On 2/26/2016 10:17 AM, Allan Herriman wrote:
On Fri, 26 Feb 2016 00:43:45 -0800, Yang Luo wrote:

eg1:
c=a*29;-->c=a*32-a*4+a-->c=a<<5-a<<2+a;
eg2:
c=a*72;-->c=a*8*(8+1)-->c=(a<<3)<<3+a<<3;
some papers researched this topic, but I didn't find any tools/codes
to do this.
Is there anybody used this way to optimazation const multiplication?


The first step, e.g. c=a*29;-->c=a*32-a*4+a seems similar to Booth's
algorithm.

https://en.wikipedia.org/wiki/Booth's_multiplication_algorithm

The other example eg2 shows a multiplication by 72 which is 64+8. I'm
not sure what the alternate form is doing any different from multiplying
by 64 and 8 and adding those results. Left shift by 3 twice is the same
as a left shift by 6 which is the same as multiplying by 64.

Why would a paper be needed to understand either of these examples?
Multiplying by constants is well understood.

And for a long time, too. E.g. Booth's algorithm dates from before I was
born.

Allan

 

[Kevin Neilson]

Do you just want the algorithm for CSD (canonical signed digit) multiplication? It's explained here:
https://en.wikipedia.org/wiki/Canonical_signed_digit

The synthesizer might even have this built in, but if not, you could certainly make an HDL function to do it.

 

[GaborSzakacs]

Kevin Neilson wrote:

Do you just want the algorithm for CSD (canonical signed digit) multiplication? It's explained here:
https://en.wikipedia.org/wiki/Canonical_signed_digit

The synthesizer might even have this built in, but if not, you could certainly make an HDL function to do it.

"CSD is obtained by transforming every sequence of zero followed by ones
(011...1) into + followed by zeros and the least significant bit by -
(+0....0-)."

It would seem that you'd need at least three ones in a row to reduce
the number of terms this way. It would be interesting to see what
synthesis does with constant multiplication for numbers that would
be more efficient to implement with CSD.

--
Gabor

 

[Kevin Neilson]

On Tuesday, March 1, 2016 at 7:35:51 AM UTC-7, gabor wrote:

Kevin Neilson wrote:
Do you just want the algorithm for CSD (canonical signed digit) multiplication? It's explained here:
https://en.wikipedia.org/wiki/Canonical_signed_digit

The synthesizer might even have this built in, but if not, you could certainly make an HDL function to do it.

"CSD is obtained by transforming every sequence of zero followed by ones
(011...1) into + followed by zeros and the least significant bit by -
(+0....0-)."

It would seem that you'd need at least three ones in a row to reduce
the number of terms this way. It would be interesting to see what
synthesis does with constant multiplication for numbers that would
be more efficient to implement with CSD.

--
Gabor

I think it works out so that the CSD representation always has zeros in at least 1/3 of the positions. I guess the worst case would be if the binary multiplicand were 0110110110... and then the CSD representation would be 0++0++0++0++0... and would end up the same.

If you're using an FPGA and the multiplicand has more than a few nonzero values, you're probably better off with a built-in multiplier.