strange power .^ operator behaviour

Take a look on this FEX.

For vectors of length greater than >~100 elements it is more efficient to use multiple x.^2 than x.^n, where n is an integer n>=3. The performance can be ~x10-x100 better depends on the vector length and power.

Looks like that MATLAB has not optimally implemented operator '.^'. Any comments regarding this strange behaviour of ".^" operator???

[Stephen23]

The topic has been discussed before:

https://www.mathworks.com/matlabcentral/answers/23164-why-square-takes-longer-than-multiplication

https://www.mathworks.com/matlabcentral/answers/364045-fast-element-wise-power

https://www.mathworks.com/matlabcentral/answers/482212-multiplication-by-0-5-vs-division-by-2

See also:

http://www.walkingrandomly.com/?p=5377

http://www.robertomontagna.it/2012/12/more-about-exponents.html

"Looks like that MATLAB has not optimally implemented operator '.^'."

It probably is for floating point numbers... which includes the power (i.e. input B) itself.

[Michal]

I am still not sure, what is the main lesson?

Power operator is definitelly not optimally implemented for integer B. So, what is the recommended way in a case of integer B? Transform the power to multiplication like this, for example:

function A = fastintpower(x,n) 
  % check if N is integer 
  if n ~= fix(n) 
      error('n is not integer'); 
  end 
  % Transform power to multiplication 
  fh= str2func(['@(x) ' repmat('x.*',[1, n-1]) 'x'] ); 
  % evaluation power 
  A = fh(x); 
end

May be, there is any other, more optimized, way ... ???

[Adam]

I'd be surprised if any function including str2func would ever be the optimal way of doing something, to be honest! There's a whole load of Matlab functions that you have to work around or rewrite yourself for certain situations, though it is sometimes surprising when the most basic of functions can be outperformed by writing more obtuse code.

[Michal]

@Adam I think this is the reason, why I am not sure that built-in power operator is implemented optimally in MATLAB.

[Adam]

Well, it demonstrably isn't, for all cases, but I don't know what the logic was behind the decision of how to implement it. Making a function behave optimally across all possible usages of it is an ill-defined problem unless it is a trivial case where one implementation is simply faster than all others in all cases. In most situations there is compromise and functions may be written to be optimal in what were considered to be the most common use cases. Whoever wrote the function or was involved on checking and signing off on it at Mathworks would be the ones most likely to be able to confirm the logic behind its implementation.

What is certain though is that the more ifs and elses and clauses you have in a function to check for certain cases and do different behaviour, the slower the function will be in a general case that didn't have those checks so it is always a trade-off.

[Michal]

Obviously, in a case of integer B you are wrong, because in this (very common) use case the built-in power operator is significantly (x10 -x100) slower than other obtuse codes.

But, may be the JIT-engine prefere in this case very spacific ways of evaluation, like transformation to multiplication. MATLAB is very complicated beast ... :)

[Adam]

For example, you could program a multiplication function like this

function result = multiply( a, b )

if all( a == 1)
    result = b;
elseif all( b == 1 )
    result = a;
else
    result = a .* b;
end

putting aside any extra complexities of multiplication, for the sake of argument. It might be faster in the case where a or b is all ones (though I suspect on a modern machine that multiplying all values by 1 may well be quicker than evaluating an if-else statement anyway), but it is guaranteed to be slower in all other cases than simply always doing

result = a .* b

putting aside compiler optimisations which may simply optimise out the extra code.

[Michal]

Integer power problem and your ad-absurdum example are two very different things ...

Instead of this meaningless discussion try to propose any good way how to effectively compute integer element- wise power of array. All MATLAB users, which are using massively the power operator '.^' on large arrays, will be very happy for any improvement.

[Stephen23]

"All MATLAB users, which are using massively the power operator '.^' on large arrays, will very happy for any improvement."

I totally agree. Start here: https://blogs.mathworks.com/community/2008/01/14/making-a-feature-request/

[Adam]

@Michal Kvasnicka - I seem to remember it was you who was making a big fuss about what should be answer vs what should be a comment not so long ago. If you want answers look in the answers section. Comments can be either read or ignored as you wish, but do at least serve the purpose of keeping your thread from falling down the board without you having to keep editing your posts regularly to achieve the same thing!

[Michal]

@Adam I did not edit any of my comment here in a way of changing its meaning. I just edit them to fix typos and so on.

Please, try to be constructive!

Answer 1

[Steven Lord]

Performance is one key metric of whether a function is "effective". If you wanted a power function that was as performant as possible, we could implement the built-in equivalent of this:

fastestPower = @(x, n) [];

Obviously that's taking things to an absurd extreme. It should go without saying but I'll say it anyway, we wouldn't do that. As one of the people who would be asked to review such a proposal that would be an OMDB (Over My Dead Body) situation. [And I can imagine how Cleve would react if someone seriously proposed that!]

But that does illustrate a serious point, that performance is not the only key metric of whether a function is "effective". Accuracy is another key metric for a function. [The absurd example above maximizes performance while minimizing accuracy.] Balancing performance and accuracy and several other key metrics across the whole spectrum of input arguments (including taking into consideration how common each use case for a function is) is a multiobjective optimization problem.

If you know of a faster algorithm that we should consider, submit it as an enhancement request through Technical Support. It may be one we have already considered and rejected for various reasons (better performance but unacceptable loss of accuracy, for example, or it only performs better in extremely specific and uncommon cases for another example.) It may be something that we evaluate (or re-evaluate) and adopt.

[Michal]

You are definitely right. Speed performance is not only metric under consideration.

But: 1. Above mentioned method (fast power on FEX) produce results with acceptable accuracy and significantly faster in a specific case of integer power and double class arrays. 2. Of course, I do not know how will be the method perform for any other types of input arrays (complex,.. ). 3. Moreover I am not sure, that this method is the optimal solution for specific case of integer power.

What I want to say is the fact, that Matlab developers should seriously reconsider this specific case, which is very common(!!!). I mean integer value of B and single or double class of array A (A.^B).

Answer 2

[Michal]

Very interesting description of the integer power problem:

http://szhorvat.net/pelican/fast-computation-of-powers.html