CODEWITHSUNDEEP
javascriptalgorithmmathdata-structures
user5711656
user5711656

Reputation: 3678

How to find power of 11 or x is power n in javascript?

I am trying to find 11 power of n. I know in JavaScript there is a function Math.pow which give you power of number.I want to implement that function by own.my function is working perfectly , but its time complexity is O(n) can we reduce that time complexity using any other method?

I am thinking to use bit map, but not getting success.

function power(x,n) {
    let sum =1
    for(let i =0;i<n;i++){
    sum*=x
    }
    
    return sum
}

console.log(power(11,3))

Upvotes: 4

Views: 1069

Answers (5)

raina77ow
raina77ow

Reputation: 106443

One possible approach:

function power(x, n) {
  let res = 1;
  let acc = x;
  while (n > 0) {
    if (n & 1) res *= acc;
    acc *= acc;
    n >>= 1;
  }
  return res;
}

console.log(power(11, 0)); // 1
console.log(power(11, 1)); // 11
console.log(power(11, 2)); // 121
console.log(power(11, 3)); // 1331
console.log(power(11, 5)); // 161051
console.log(power(11, 8)); // 214358881 etc.

The idea is memoizing the results of subsequent squaring of the original number (x). At each step n is halved, so it's O(log n) instead of O(n). It's quite similar to @NinaScholz solution, but is iterative, not recursive (which I actually consider a benefit).

(and yes, in any real world app there should definitely be a check for MAX_SAFE_INTEGER as well, but I suppose we're discussing an algorithm here)

Upvotes: 2

Nina Scholz
Nina Scholz

Reputation: 386680

You could take the proposed square approach.

The complexity is O(log2(n)), like this table with the counts of the function.

   n     counts
-------  ------
   100      7
  1000     10
 10000     14
100000     17


function power(x, n) {
    if (n === 1) return x;
    let temp = power(x, n >> 1);
    return n % 2
        ? x * temp * temp
        : temp * temp;
}

console.log(power(11, 3)); // 1331 with 2 calls

Upvotes: 2

Greedo
Greedo

Reputation: 3559

Here is a straightforward JS implementation of the squre approach:

function exp_by_squaring(x,n){
   if(n < 0) 
     return exp_by_squaring(1 / x, -n);
   else if(n === 0) 
     return  1;
   else if(n === 1) 
     return  x ;
   else if(n %2===0) 
     return exp_by_squaring(x * x,  n / 2);
   else 
     return x * exp_by_squaring(x * x, (n - 1) / 2);
}

I also created a benchmark with some of the approaches from other answers, have a look:

Benchmark

Upvotes: 1

user14061659
user14061659

Reputation: 1

This appears quicker than your original implementation, although not elegant

function power(x,n){
   return Array.apply(null,Array(n)).reduce((r,v) => r*x, 1)
}

Upvotes: -1

Rick van den Broek
Rick van den Broek

Reputation: 197

I am not yet able to just comment on your question but I hope I understand your question good enough. Is this something you are looking for?

const myPow = (x, y) => x ** y;

Upvotes: -2

Related Questions