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?

 

[Daniel Kho]

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

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

 

[Nikolaos Kavvadias]

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 ;
}

To get this result, I ran it with

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



Hope this helps.

Best regards,
Nikolaos Kavvadias

 

[Yang Luo]

thanks a lot.