Szabolcs Horvát

MENU
  • About
  • Publications
  • Software
  • Photos
  • Links
  • Notes

Fast computation of integer powers

Fri 17 February 2017
By szhorvat

In Notes.

tags: tipsprogramming

How many multiplications are needed to calculate \(x^6\)? The naïve way to do it is \(x^6 = x\cdot x\cdot x\cdot x\cdot x\cdot x\). That is five multiplications. But we can do better: \((x\cdot x\cdot x)^2\) only requires three. Using as few operations as possible is important for the efficient evaluation of expressions on a computer. Is there a general way to find the smallest number of multiplications needed to compute any given power \(n\)?

read more ...

There are comments.