# const multiplication using shift and add solve

## Ask a question - edaboard.com

elektroda.net NewsGroups Forum Index - VHDL Language - const multiplication using shift and add solve

Yang Luo
Guest

Fri Feb 26, 2016 10:44 am

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?

Daniel Kho
Guest

Fri Feb 26, 2016 3:28 pm

On Friday, 26 February 2016 16:44:30 UTC+8, Yang Luo wrote:
Quote:
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?

Is that a sequence of steps? Maybe you want to make a statemachine or case statement to do the sequencing. But assuming you have a and c declared as either integer, or u_signed, you could have:
c <= a * 29;
....
c <= (a * 32) - (a * 4) + a; -- added parentheses for clarity
....
c <= (a sll (5 - a)) sll (2 + a);

I may have missed something, but you get the idea. Similarly, you can do for eg2.
Just rewrite the syntax in VHDL, and get familiarised a bit with hardware design.

- daniel

Guest

Fri Feb 26, 2016 3:31 pm

Hi!

> Is there anybody used this way to optimazation const multiplication?

sure, please check the kmul tool: http://github.com/nkkav/kmul

You can build it in any unix-like platform. For guidance please consult the README.md that comes with it.

For instance, the tool says that a * 29 would be implemented as:

signed int kmul_s32_p_29 (signed int x)
{
signed int t0;
signed int t1;
signed int t2;
signed int t3;
signed int t4;
signed int y;
t0 = x;
t1 = t0 << 3;
t2 = t1 - x;
t3 = t2 << 2;
t4 = t3 + x;
y = t4;
return (y);
}

To get this result, I ran it with

../kmul.exe -mul 29 -signed -ansic

Hope this helps.

Best regards,