Processing math: 100%

Szabolcs Horvát

MENU

About
Publications
Software
Photos
Links
Notes

Fast computation of integer powers

Fri 17 February 2017

By szhorvat

In Notes.

tags: tips programming

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$ ?