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.