6
$\begingroup$

I recently discovered that, in MATLAB 2013b at least, it is significantly faster to do repeated multiplication rather than integer powers. That is, 

tic;test4p = a.^4;toc

is much slower than

tic;test4m = a.*a.*a.*a;toc

See http://www.walkingrandomly.com/?p=5377 for full details. Is there any numerical reason (accuracy etc) why repeated multiplication might be a bad idea?

Improve this question
$\endgroup$
2
  • $\begingroup$ Are you sure that matlab is using integer powers? If you try with a biger number (20) test4p is taking amost the same time but test4m is taking much more than before. $\endgroup$ – sebas Feb 27 '14 at 0:36
  • $\begingroup$ What happens if you try a.^3.14 ? If MATLAB is using a general purpose exponentiation routine (e.g. by using log() and exp()), then it should take the same time as a.^4. $\endgroup$ – Brian Borchers Feb 27 '14 at 4:58
4
$\begingroup$

I'm surprised that MATLAB does not do exponentiation-by-squaring for positive integer powers, since that algorithm should require fewer multiplications. I think a consequence of that should be that numerical errors accumulate less quickly.

Optimal addition-chain multiplication of exponents is an NP-complete problem, so it's not worth it to figure out the sequence of multiplies and exponentiations that minimizes the total number of multiplicative operations.

Improve this answer
$\endgroup$
6
$\begingroup$

the numeric reason would be the loss precision. at each multiplication you lose a little bit of precision. If you want to implement power by multiplication, then it's better to look up the algorithm. I once coded the algorithm from Stepanov's "Elements of Programming" book, it's the fastest possible way.

UPDATE: I found the earlier version of Stepanov's book as Notes

Search for fast_power algorithm in section 10.3. It's so beautiful, one of the most elegant pieces of code ever

Improve this answer
$\endgroup$
2
  • $\begingroup$ His algorithm is essentially exponentiation by squaring with some additional implementation-level optimizations. $\endgroup$ – Geoff Oxberry Feb 27 '14 at 4:42
  • $\begingroup$ Yes. It's much faster than the stock algorithm. I had an accounting application where the powers were always integer numbers, so it worked fine for me. $\endgroup$ – Aksakal almost surely binary Feb 27 '14 at 12:36

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.