Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
What is the number of floating point operations needed to perform exponentiation (power of)?
Assuming multiplication of two floats use one FLOP, the number of operations for $x^n$ will be $n-1$. However, is there a faster way to do this? How does it work if $n$ isn't an integer?
Assuming multiplication between two numbers use one FLOP, the number of operations for $x^n$ will be $n-1$. However, is there a faster way to do this ...
There most certainly is a faster way to do this for non-negative integer powers. For example, $x^{14}=x^{8}x^{4}x^{2}$. It takes one multiplication to compute $x^2$, one more to compute $x^4$, one more to compute $x^8$, and two more to multiple those three numbers. This suggests a simple cost and a simple algorithm.
This yields a concise algorithm for any non-negative integer power. This algorithm is the most efficient, up to $x^{14}$. This algorithm suggests six multiplications are needed to compute $x^{15}$ since $x^{15}=x^8x^4x^2x$. However, 15 is 120 in base 3 and 30 in base 5, both of which imply that only five multiplications are needed to compute $x^{15}$: $x^{15}=(x^3)^4x^3$ from the base three representation, and $x^{15}=(x^5)^3$ from the base five representation. The minimum number of multiplications needed to compute $x^n$ where $n$ is a non-negative integer is in fact an NP-complete problem. But it's a whole lot less than $n-1$ multiplications.
... and how does it work if $n$ isn't an integer?
There are some tricks one can use if $n$ is a rational. But if $x$ is real and $n$ is a non-negative real, one must resort to approximation techniques. (For example, approximation techniques are used twice-fold in calculating $\exp(n\ln(x))$.)
Using n-1 multiplications would be rather daft. For example, if n = 1024, you just square x ten times. Worst case is 2 * log_2 (n). You can look up Donald Knuth, Art of Computer Programming, for some details how to do it faster. There are some situations, like n = 1023, where you would square x ten times giving x^1024, then divide by x.
You can use the formula $$ x^y = \exp (y \ln x). $$
If you want to use only multiplications, when $n$ is a natural number you can use repeated squaring, that uses $O(\log n)$ multiplications. For other $n$, multiplication alone doesn’t suffice.
People told you what happens when $n$ is an integer.
Regarding when it isn't, there may not even exist a way to do floating-point exponentiation at all.
It's called the Table-Maker's Dilemma, which says the amount of memory you'd need is unbounded:
No general way exists to predict how many extra digits will have to be carried to compute a transcendental expression and round it correctly to some preassigned number of digits.
Even the fact (if true) that a finite number of extra digits will ultimately suffice may be a deep theorem.
pow(x,y) for some inputs. It tried very hard (arguably tried too hard) to chase down the elusive half an ULP accuracy.
$\endgroup$
– David Hammen
Mar 3 '19 at 19:14
If you are serious about the problem, you may not try to find a solution with the lowest number of multiplications, but with the lowest execution time.
Consider a model where you can start a multiplication in every cycle, but each multiplication takes a fixed number of cycles, say 3 cycles. A method calculating x^n with k multiplications might take 3k cycles (if each multiplication depends on a result that was calculated just before), while a a method using more multiplications might run quicker.
For example: To calculate x^15, you might calculate in that order x^2 = x*x, x^3 = (x^2)*x, x^6 = (x^3)^2, x^7 = x^6 * x, x^14 = (x^7)^2, x^15 = x^14 * x. Six multiplications, but each dependent on the previous one.
Or you calculate x^2, x^4 = (x^2)^2, x^3 = x^2 * x, x^5 = (x^4)*x, x^15 = x^5 * x^3, so you have only four multiplications depending on previous results.
