3

I have an assignment where I basically need to count the number of floating point operations in a simple program, which involves a loop, a matrix, and operations such as *, + and ^.

From my understanding, a floating-point operation is an operation that involves floating-point numbers, and we may be interested in counting these operations because I think they may be more expensive for the computer. If you want to add more details to this part, it would be nice.

My problem is that I've no idea of knowing exactly which operations involve floating-point numbers, unless I use functions, such as isfloat. In that case, would just one of the numbers in the operation be necessary to be floating-point to the operation be considered a floating-point operation, right? If not, why? Can you add more details on this?

For example, suppose I've the following simple function:

function [r, n] = naive(c, x)
% c is the vector of coefficients of the polynomial
% The coeffiecients should be given as follows
% c(1) = coefficient of x^0 (or 1).
% c(length(c)) = coefficient of the largest power of x
% x is the point to evaluate the polynomial at
% r is the result of the evaluation
% (Assumes that the entries are integers)

r = c(1);
n = 0;

for i=2:length(c)
    r = r + c(i) * x^(i - 1);
    n = n + 2 + (i - 1);
end

end

which basically calculates a normal polynomial evaluated at x given the coefficients in a vector c.

As you can see from the code, n is actually keeping track of floating-point operations. But actually, I'm counting every mathematical operation (except the assignment) as a floating-point operation, but this of course might not be right, or is it? If yes or no, why?

Both the coefficients and c might be floating-point numbers. So, instead of counting every operation as a floating point operation, should we first check with for example isfloat if the numbers are floating point, and only then increment n?

Note, I'm aware of the function flops, which, from what I understood, it should count the floating-point operations, but it's deprecated, and mostly I would like to learn better these concepts, and therefore try to count them manually.

Thanks for any help!

nbro
  • 15,395
  • 32
  • 113
  • 196
  • I think you are over-counting by one in each iteration. There are `i-1` multiplications and one addition. – Patricia Shanahan Mar 04 '16 at 12:28
  • @PatriciaShanahan That might be correct, since x^y = x*x*...*x, that is we have `y` `x`s, but the multiplications are just `y - 1`. – nbro Mar 04 '16 at 14:12
  • Another way to think of it: Write a list of the terms that need to be multiplied, y followed by i-1 instances of x, a total of i terms. Now put a multiplication sign between each pair of terms. You will have i-1 multiplication signs. – Patricia Shanahan Mar 04 '16 at 15:53
  • @PatriciaShanahan By the way, do you have any ideas regarding my other doubts/problems? – nbro Mar 04 '16 at 16:09
  • FYI, the `flops` function was deprecated way back in 2000 for reasons detailed in [this article](http://www.mathworks.com/company/newsletters/articles/matlab-incorporates-lapack.html?s_tid=srchtitle) (see near end) by MathWorks founder Cleve Moler. This is a fine exercise, but you (and your instructor) should be aware it may not be a useful to characterize Matlab performance (even more so with modern JIT compilation). – horchler Mar 04 '16 at 16:09
  • You are not counting every mathematical operation. Evaluating c(i) naively uses an integer multiply and add. I would expect Matlab to do the optimizations to reduce the in-loop operations to an integer add. – Patricia Shanahan Mar 04 '16 at 20:03
  • @PatriciaShanahan So, what do you think? Should I also count `c(i)` as more 2 floating-point operations? In general, is there a good documentation for extracting this information (like the one you gave me), i.e. how many floating-point operations are actually used for misleading operations like indexing? – nbro Mar 04 '16 at 21:56
  • No, you should not count them as floating point operations, because they are likely to be integer operations. Mainly I'm trying to illustrate the difficulties of dealing optimization. What if Matlab notices that you can use one of the intermediate results from the previous iteration to reduce the cost of calculating the exponent? – Patricia Shanahan Mar 04 '16 at 23:24
  • @PatriciaShanahan Yes, indeed, this kind of exercises are a little bit misleading because it depends also on the underlying implementation...and we cannot know for sure everything, unless we have a look at the source code. – nbro Mar 05 '16 at 00:31
  • There is a Matlab [function][1] over on the file exchange which sounds like it does something similar. You might be able to look into their script to see how it operates and pull some thoughts/ideas from there. Again...this is a comment, not an answer. I just wanted to add my input. [1]: http://www.mathworks.com/matlabcentral/fileexchange/50608-counting-the-floating-point-operations--flops- – ThatsRightJack Mar 13 '16 at 07:39

0 Answers0