Estimating the complexity by the calculation of the number of real multiplications in a general polynomial function

For the following memory polynomial equation,

$$y(n)=\displaystyle\sum_{m=0}^{M-1}\displaystyle\sum_{p =1\\p\,\textrm{odd}}^{P}a_{m_p} \, x(n-m) \, |x(n-m)|^{(p-1)}$$

The total number of coefficients is $$M\frac{(P+1)}{2}$$

I need to calculate:

1- the total number of complex multiplications

2- the total number of real multiplications

• The polynomial function does not seem fully generic to me (because of odd terms). Is that homework? What were your progress so far? Jan 3, 2020 at 10:09

First, if you have to evaluate all powers $$y^0,y^1,\,\cdots,y^Q$$, you can store the power-of-two powers, and use the binary expansion of a power $$q$$. It can be called exponentiation by squaring. For instance, to compute $$y^7$$, you need one multiply for $$y^2 = y\times y$$, one for $$y^4=y^2\times y^2$$ and two more for $$y \times y^2 \times y^4$$, so four multiplies instead of six by direct computation. And the $$y^2$$ and $$y^4$$ can be stored for the next powers.
$$a_0 x^n + a_1 x^{n-1} + \cdots + a_n = \left(\left(\left( a_0x+a_1\right) x \right)\ldots a_{n-1}\right)x+ a_n$$ which can be adapted to your case.