6
$\begingroup$

I was watching a lecture and got confused over a slide. This is what it says:

Consider a polynomial - first representation

$$P = 2 + 4x^{3} + 8x^{6} + 7x^{25} + 6x^{99}$$

enter image description here

  • The space complexity is 100 memory locations.
  • The time complexity is:
    • Access lookup operations: 100
    • Multiplication operations: 4 + 7 + 26 + 100 = 137
    • Addition operations: 5
    • Total operations: 242

I don't get how the number of multiplication operations are counted. For example, if we consider $x^{3}$ then it should have just two multiplications, right? Such as $x \times x \times x$, isn't it?

Addition operation is 5 or 4...I think its 4?

$\endgroup$
  • 1
    $\begingroup$ It seems that you are right regarding the number of needed additions and multiplication when the result is computed naively.: 4 multiplications should be 3, and 5 additions should be 4. Unless I am missing a point. But you should edit your question to replace image by text. $\endgroup$ – babou Jul 15 '15 at 12:59
  • $\begingroup$ @Raphael Well I am sorry for my image post ,I couldn't think in that details .thanks for pointing it out with a logical reason of post becoming more search friendly though I am all new to use LaTeX but i will try to edit my image back to text.Actually I just joined cs.stackexchange So if you don't mind then I would request that kindly take back your down vote .Further as you questioned the use of word "complexity" here then I have same question like what babou asked . $\endgroup$ – Shashi Jul 15 '15 at 14:04
  • $\begingroup$ Glad it helps, but do not trust me, or anyone else too much. Regarding downvote, you cannot presume it was done by Raphael. The more critical people are not necessarily those who downvote. People may remove their downvote when you edit your post appropriately, but often not. But it changes little for you. I would use the word "cost" rather than "complexity", but not being a specialist, I wondered whether there was another word, especially when considering one instance of applying an algorithm. $\endgroup$ – babou Jul 15 '15 at 14:18
  • 2
    $\begingroup$ There's still that attribution missing. $\endgroup$ – Raphael Jul 15 '15 at 14:25
  • $\begingroup$ How is 4 + 7 + 100 = 136? Please make more effort transcribing the figure. $\endgroup$ – Yuval Filmus Jul 15 '15 at 14:56
5
$\begingroup$

I am not sure what the slide was intended for, so I just gave a straight answer to your question in a comment, viz that the slide really intended 3 multiplications for $4x^3=4\times x\times x\times x$, and 4 additions to add the five terms.

Now of course, there are better ways to do that. Various powers of $x$ can be obtained in multiplying other powers of $x$ together using the rule $x^m\times x^n=x^{m+n}$.

The method of repeated squaring presente by David Richerby in his answer is a systematic way to get high powers of $x$ as fast as possible. However, when you need a few specific powers, you can try to adapt it to compute just these powers with as few multiplications as possible.

So you can compute, for example:

$\begin{align} x^2&=x\times x \\ x^3&=x^2\times x \\ x^6&=x^3\times x^3 \\ x^{12}&=x^6\times x^6 \\ x^{24}&=x^{12}\times x^{12} \\ x^{25}&=x^{24}\times x \\ x^{49}&=x^{24}\times x^{25} \\ x^{50}&=x^{25}\times x^{25} \\ x^{99}&=x^{49}\times x^{50} \end{align}$

Hence you get all needed powers of $x$ with only 9 multiplications of powers of $x$, to which you have to add 4 multiplications for the coefficients, which makes a total of 13 multiplications. The number of additions remains at 4.

But you can do a bit better using a technique that is most efficient when all powers of $x$ are being used, rather than having a sparse polynomial. The technique, known as Horner's method, consists in factorizing some powers of the variable, when it helps the computation.

In the case of your sparse polynomial, you may notice that $7x^{25}+6x^{99}=x^{25}(7+6x^{74})$. Hence rather than computing $x^{50}$ and $x^{99}$, you compute only

$x^{74}=x^{49}\times x^{25}$ and then $x^{25}(7+6x^{74})$.

This saves one multiplication, because both $7x^{25}+6x^{99}$ and $x^{25}(7+6x^{74})$ take exactly 2 multiplications and one addition, assuming the powers of $x$ are already computed, but computing the needed powers takes one less multiplication.

So you are down to a total of 12 multiplications and 4 additions.

I do not see any way to do better on this example, but I have no systematic algorithm to check that. However, I am rather confident that someone must have worked on it.

BTW, what was the theme of the set of slides?

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

Yes, there's an error on the slide: as you say, there are only four addition operations (count the plus signs!) and, e.g., computing $4x^3 = 4\times x\times x\times x$ requires only three multiplications, not four.

However, there is a more significant point to be made, which is that computing, say, $8x^6$ does not require six multiplications. We have $8x^6 = 8\times z\times z\times z$, where $z = x^2$. This requires only four multiplications: one to compute $z$ and then three more to compute $8z^3$. And $x^{99} = z_0\times z_1 \times z_5\times z_6$, where $$z_i = x^{2^i} = \begin{cases} x &\text{if $i=0$}\\ z_{i-1}^2 &\text{otherwise.}\end{cases}$$ So this can be computed with only nine multiplications (six to produce $z_1, \dots, z_6$ and three more to compute $x^{99}$ from those. This technique is known as exponentiation by (repeated) squaring.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

I think they are multiplying the constants too.

  1. 4*x...*x (3 times)= 3
  2. 8*x*....*x(6 times)= 6
  3. 7*x*....*x(25 times)= 25
  4. 6*x*....*x (99 times)= 99

Addition operations are 4.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You don't need six multiplications to compute $8x^6$. $8x^6 = 8\times z\times z\times z$, where $z=x^2$: that's only four multiplications (one to compute $z$ and three more to compute $8z^3$). And $4z^{99}$ needs many fewer than $99$ multiplications: see repeated squaring. $\endgroup$ – David Richerby Jul 16 '15 at 10:41
0
$\begingroup$

The claims of this slide seem bizarre.

First, even using repeated multiplication to calculate powers, x^99 requires 98 multiplications, and 6x^99 requires 99. Not 100.

But then you would use the result of x^25, so x^99 would only require 74 more multiplications. With 98 multiplications, you get all the required powers, and with the four coefficients, it makes a total of 102 multiplications and 4 additions.

But nobody would calculate x^99 that way. See babou's post.

Now if all coefficients were non-zero, it seems their method would use about 5,000 multiplications, which is just ridiculous.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This is describing one slide. Thus it is to be expected that there are other slides that explain that there are better ways. We cannot draw any conclusion from a statement out of context. The point of the question was that, even considering the most naive evaluation method, there was still one extra multiplication and one extra addition that cannot be accounted for. Unfortunately, the poster of the question will not tell what the series of slides was for, nor give a reference, so we cannot know more. I did ask him. $\endgroup$ – babou Jul 18 '15 at 9:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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