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

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

1 Answer 1


The direct computation should be straightforward. Since I suspect the exercice has other purposes (more advanced algorithmic complexity), there additionally are a couple of tricks to reduce the complexity of power evaluations.

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.

Second, a classical polynomial evaluation is "Horner's scheme":

$$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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.