7
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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.

  • Convert the non-negative integer power to base 2.
  • Count the number of ones in this representation.
  • Add the power of two corresponding to the most significant non-zero bit in this representation.
  • Subtract one.

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))$.)

$\endgroup$
  • $\begingroup$ Are you sure calculating the number of multiplications needed in NP-complete? This seems like a problem dependent on factorization, which is believed to be NP-Intermediate. $\endgroup$ – stux Mar 3 at 3:46
  • $\begingroup$ Do you have a reference for the complexity of addition chains? $\endgroup$ – Yuval Filmus Mar 3 at 7:29
  • $\begingroup$ @stux: Just because factorizations yield candidate solutions does not imply that all solutions are based on factorization... $\endgroup$ – user21820 Mar 3 at 8:54
  • $\begingroup$ @user21820: that is very true, hence my question and wording. If all solutions are driven by factorization then the problem (most likely) cannot be NP-complete. If it isn't, then the link provided does not include a reference proving NP-completeness. $\endgroup$ – stux Mar 3 at 18:00
  • 2
    $\begingroup$ @stux - Downey, Peter, Benton Leong, and Ravi Sethi. "Computing sequences with addition chains." SIAM Journal on Computing 10.3 (1981): 638-646. $\endgroup$ – David Hammen Mar 3 at 19:27
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, don't know why that didn't come to my mind... $\endgroup$ – Mr. Eivind Mar 2 at 17:14
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ For floating point arithmetic it is obvious that a finite number of extra digits will suffice, because there is a finite set of inputs. $\endgroup$ – gnasher729 Mar 3 at 13:23
  • $\begingroup$ @gnasher729: Yeah... I wouldn't have posted this on StackOverflow, but given this was on CS.SE, I wasn't sure how literally to interpret the word "floating-point" in the question. I thought there's a decent chance it was just used as a synonym for "non-integer" so I figured I'd mention the transcendental case for completeness. $\endgroup$ – Mehrdad Mar 3 at 13:35
  • 1
    $\begingroup$ Possibly closely related to this is the (former) extraordinary slowness of the former gcc math library implementation of 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 at 19:14
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The last paragraph is erroneous. $x^5*x^3$ is $x^8$, not $x^{15}$. Calculating $x^{15}$ requires at least five multiplications (or four multiplications to yield $x^{16}$, followed by a division by $x$, but that's more expensive than five multiplications). $\endgroup$ – David Hammen Mar 3 at 18:57

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.