Flop computation clarification

Question

Can someone clarify this for me? Suppose I wanted to use MATLAB to compute a polynomial, i.e., $(x-3)^{5}$. Would this count as 5 subtractions and 4 multiplications, or does the computer only subtract once, and then take the 5th power?

Answer 1

Try something like:

x=1:100000000;
t=cputime ; x.**5 ; cputime-t
t=cputime ; x.**5 ; cputime-t
t=cputime ; x.**5 ; cputime-t
t=cputime ; ((x.**2).**2).*x ; cputime-t
t=cputime ; ((x.**2).**2).*x ; cputime-t
t=cputime ; ((x.**2).**2).*x ; cputime-t

In Octave on my x201t I get consistently lower numbers for the binary powered method (roughly 1.72 s for the first, 1.65 s for the second).

I would be a little surprised if they performed 'strength reduction' like that with floating point operations, purely on the basis that it would be doing something different than asked by the user. (However, I would be hard pressed to give a convincing example of why computing $x^n$ using squaring would result in a significantly different answer to repeated multiplication.)

Since flops no longer works, I'm not sure how to count operations exactly. I would suspect the answer to your question is one subtraction and four multiplications.