Why is this code bad to calculate the power (less efficient)?

Question

class Solution {
   public:
      double myPow(double x, int n) {
         double result=1;
         bool neg=false;

         if(n<0)
         {
            n = -1*n;
            neg=true;
         }
         for(int i =1; i<=n;i++)
         {
            result = x*result;
         }  
         if(neg)
         {
            result = 1/result;
         }
         return result;
      }

};

You might do something like `pow(x, 4)` -> `pow(pow(x, 2), 2)`, instead of `x * x * x * x`. — Jarod42, Sep 23 '19 at 16:27
Also in C++ you can have stand-alone functions in addition to methods — lost_in_the_source, Sep 23 '19 at 16:29
This is a faster technique https://en.wikipedia.org/wiki/Exponentiation_by_squaring for non-negative `n` (and recasting the problem for the negative n case is trivial). Writing `pow(x, n)` as `exp(n log x)` might be faster too, but check for floating point naughties. — Bathsheba, Sep 23 '19 at 16:30
@Jarod42 I would rephrase - `pow(x, n) = pow(x, n/2)^2` for even `n`s...multiply by `x` for odd ones. — Eugene Sh., Sep 23 '19 at 16:30
in addition to what has been said already, your code is bad, because you are reinventing the wheel. `std::pow` does what you need and unless you have a good reason to write your own you shouldnt (though I guess having this as a homework task is reason enough ;). — 463035818_is_not_an_ai, Sep 23 '19 at 16:32
if you want to put it in a class then at least declare the method as `static`, currently one needs to create an instance for no gain — 463035818_is_not_an_ai, Sep 23 '19 at 16:33
see [Power by squaring for negative exponents](https://stackoverflow.com/a/30962495/2521214) there are more options how to calculate each of which is faster than yours ... using better complexities ... — Spektre, Sep 25 '19 at 06:38

score 8 · Answer 1 · edited Sep 23 '19 at 17:38

8

Your method uses O(N) operations to compute the power.
It is possible to compute the power in O(log(N)) operations.

For that reason, it is not the most efficient.

The logic for converting it to O(log(N)) operations can be seen at https://en.wikipedia.org/wiki/Exponentiation_by_squaring.

The core idea is that

To make this logic work, you need to move the code that computes the power to a positive value to its own function, which can be recursive.

      double myPowPositive(double x, int n) {
         // Use the efficient algorithm.
      }

      double myPow(double x, int n) {
         double result=1;
         bool neg=false;

         if(n<0)
         {
            n = -1*n;
            neg=true;
         }

         result = myPowPositive(x, n);

         if(neg)
         {
            result = 1/result;
         }
         return result;
      }

edited Sep 23 '19 at 17:38

Aykhan Hagverdili

28,141
6
41
93

answered Sep 23 '19 at 16:30

R Sahu

204,454
14
159
270

Not for negative n though? – Bathsheba Sep 23 '19 at 16:31
@Bathsheba, the OP computes the power to a positve value first, and then does `1/result`. – R Sahu Sep 23 '19 at 16:32
Indeed, but one needs to point out these trivialities. Have an upvote all the same. – Bathsheba Sep 23 '19 at 16:33

score 0 · Answer 2 · answered Sep 23 '19 at 16:30

I'm not providing code, because this is clearly a homework question, but I hope to guide you towards the correct solution.

The problem is that the core for loop requires n multiplications. The usual way of doing this is to loop through the bits in n, multiplying by x if the bit is set, and squaring x each time you move on to the next bit. This requires O(ceil(lg(n))) multiplications.

score -1 · Answer 3 · answered Sep 23 '19 at 16:30

-1

You cannot really stop the loss of precision in a denominator unless you know its prime factors. This is why it is not a good choice to try this exercise for a denominator (negative exponents), but to try it for numerators (positive exponents) first.

answered Sep 23 '19 at 16:30

C. R. Ward

93
5

Why is this code bad to calculate the power (less efficient)?

3 Answers3