Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > sci.image.processing > #4090 > unrolled thread

const multiplication using shift and add solve

Back to article view | Back to sci.image.processing

Contents

  const multiplication using shift and add solve Yang Luo <youngluoyang@gmail.com> - 2016-02-26 00:47 -0800
    Re: const multiplication using shift and add solve Martin Brown <|||newspam|||@nezumi.demon.co.uk> - 2016-02-26 12:19 +0000

#4090 — const multiplication using shift and add solve

in image processing, we usually use filtering, and filter coef most is a const number. so we can do like this:
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?

[toc] | [next] | [standalone]

#4091

On 26/02/2016 08:47, Yang Luo wrote:
> in image processing, we usually use filtering, and filter coef most is a const number. so we can do like this:
> 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?

It is quite common for optimising compilers to do tricks like this for 
the original constant multiplication code

c = a*29

If you try to micromanage things explicitly in a HLL the compiler can 
get confused and generate much worse code. See strength reduction.

Typically they use something like Load Effective Address.

Much more worthwhile is vectorising some filter operations on pixels so 
that they may be performed in parallel by SIMD instructions.

Few optimising compilers can do this reliably without help.

Papers on doing an optimisation to convert multiplies to the smallest 
number of shift and adds across a set of filter coefficients also exist 
(eg):

https://users.ece.cmu.edu/~yvoronen/pubs/synth.pdf

-- 
Regards,
Martin Brown

[toc] | [prev] | [standalone]

Back to top | Article view | sci.image.processing

csiph-web