How do I calculate the exponent of a certain number without multiplying it by itself over and over again?

Question

I have a number 'x' raised to 'n', and I want to calculate the x^n without x.x.x.x....(n times). How do I do that? Is it possible to do it without the tedious self-multiplication?

(I mean to do it without computers)

I've been suggested using logarithms, but how efficient are they and do they have a limit?

Thanks!

Answer 1

This can be achieved in O(lg(n)) time:

    double exponent(double x, uint32_t n)  {
        double result = 1.0;
        while (n > 0u)
        {
           if ((n % 2) == 1)
           {
              result *= x;
              n--;
           }
          n = n / 2;
          x = x * x;
        }
        return result;
    }

Answer 2

Here's @Vectorizer 's $O(\log n)$ solution as a recursive function. $$\mathrm{pow}(x,n) = \begin{cases} x & \textrm{, if } n=1\\ \mathrm{pow}\left(x^2,\dfrac{n}{2}\right) & \textrm{, if } n \textrm{ is even}\\ x\cdot \mathrm{pow}\left(x^2,\dfrac{n-1}{2}\right) & \textrm{, if } n \textrm{ is odd} \end{cases}$$