-1
$\begingroup$

Let $x \in \mathbb{R}$ and $k \in \mathbb{Z}^+ \cup \{0\}$ then how fast can one compute $x^k$?


If $x, k \in \mathbb{Z}$ then I guess this previous discussion already settled that, How many operations at maximum needed to compute powering of a number, i.e. $N^k$?

$\endgroup$
  • 1
    $\begingroup$ What is your model of real computation? $\endgroup$ – Yuval Filmus Apr 26 '16 at 16:27
  • $\begingroup$ Those are the things that are not clear to me :) It would be great if you could kindly explain! For a specific purpose I have in mind you can as well assume that $x$ is being obtained as the inner product of two d-dimensional real vectors of bounded norm. $\endgroup$ – gradstudent Apr 26 '16 at 16:34
  • 1
    $\begingroup$ I suggest you do some reading first on the area. There are at least two or three different models. If I remember correctly there is a list somewhere on cstheory. $\endgroup$ – Yuval Filmus Apr 26 '16 at 16:37
1
$\begingroup$

There are several methods given in wikipedia article https://en.wikipedia.org/wiki/Exponentiation_by_squaring.

If both $x,k \in \mathbb{R}$, then you can compute $x^k$ as $e^{k \log x}$ as there are somewhat efficient algorithms for $e^x$ and $\log x$.

$\endgroup$

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.