Discovering the power of 11 or determining a variable raised to a specified power in JavaScript

Question

Discovering the power of 11 or determining a variable raised to a specified power in JavaScript

I am currently working on finding the power of a number, specifically 11 to the power of n. While JavaScript has the built-in function Math.pow, I have created my own function that works perfectly. However, it has a time complexity of O(n). Is there a way to reduce this time complexity using a different method?

I have considered using a bit map but have not been successful in implementing it.

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

console.log(power(11,3))

javascript algorithm math data-structures

Answer 1

Answer №1

Consider implementing the suggested square method.

The time complexity is O(log₂(n)), as shown in this table detailing the function counts:

   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)); // Result: 1331 with 2 recursive calls

Answer 2

Consider implementing the suggested square method.

The time complexity is O(log₂(n)), as shown in this table detailing the function counts:

   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)); // Result: 1331 with 2 recursive calls

Answer 3

Answer №2

Here is a potential strategy:

function calculatePower(x, n) {
  let result = 1;
  let accumulator = x;
  while (n > 0) {
    if (n & 1) result *= accumulator;
    accumulator *= accumulator;
    n >>= 1;
  }
  return result;
}

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

The concept involves storing the results of each squared iteration of the original number (x). With each step, n is halved, resulting in an O(log n) complexity instead of O(n). This approach bears resemblance to @NinaScholz's solution but is iterative rather than recursive, which may be deemed advantageous.

(It is advisable to include safeguards for MAX_SAFE_INTEGER in any real-world application, though we are primarily focusing on the algorithm here)

Answer 4

Here is a potential strategy:

function calculatePower(x, n) {
  let result = 1;
  let accumulator = x;
  while (n > 0) {
    if (n & 1) result *= accumulator;
    accumulator *= accumulator;
    n >>= 1;
  }
  return result;
}

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

The concept involves storing the results of each squared iteration of the original number (x). With each step, n is halved, resulting in an O(log n) complexity instead of O(n). This approach bears resemblance to @NinaScholz's solution but is iterative rather than recursive, which may be deemed advantageous.

(It is advisable to include safeguards for MAX_SAFE_INTEGER in any real-world application, though we are primarily focusing on the algorithm here)

Answer 5

Answer №3

Check out this simple JavaScript code for implementing the square method:

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

I have also put together a performance test comparing different techniques mentioned by other users. Feel free to take a look:

Performance Test

Answer 6

Check out this simple JavaScript code for implementing the square method:

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

I have also put together a performance test comparing different techniques mentioned by other users. Feel free to take a look:

Performance Test

Answer 7

Answer №4

Although not as elegant as some other solutions, this implementation is faster than the original.

const calculatePower = (base, exponent) => {
   return Array.apply(null, Array(exponent)).reduce((result, value) => result * base, 1);
}

Answer 8

Although not as elegant as some other solutions, this implementation is faster than the original.

const calculatePower = (base, exponent) => {
   return Array.apply(null, Array(exponent)).reduce((result, value) => result * base, 1);
}

Answer 9

Answer №5

Unfortunately, I am unable to directly leave a comment on your inquiry at the moment. However, I will try my best to provide a helpful response to your question. Does this align with what you were seeking?

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

Answer 10

Unfortunately, I am unable to directly leave a comment on your inquiry at the moment. However, I will try my best to provide a helpful response to your question. Does this align with what you were seeking?

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

Discovering the power of 11 or determining a variable raised to a specified power in JavaScript

Answer №1

Answer №2

Answer №3

Answer №4

Answer №5

Similar questions

What about handling flow control and threading with Opa?

Accept JSON data in ASP.NET MVC action method for posting data

Tips on deleting CSS comments from a CSS file

Issues with CSS transparent color overlay fading on iOS device (Note: Since the original

Validation Express; the error variable is not defined in the EJS

Generating a string indicating the range of days chosen

Incorporate attributes into object properties in a dynamic manner

Customizing an image with personalized text and then sending it to a server using a combination of javascript and

Is it possible to retrieve local variable JSON arrays using ajax/getJson()?

Error: Unable to locate module: Issue: Unable to find '../components/charts/be.js' in '/vercel/workpath0/my-app/pages'

What is the best approach for implementing component composition in AngularJS that resembles the render props pattern seen in React?

Exploring the capabilities of JW Player 6 for seeking and pausing video

Regular expression that allows alphanumeric characters and spaces, but does not permit spaces at the beginning or end of the

Why is the Javascript code outputting undefined and NaN during execution?

Transforming a jQuery menu into an active selection with Vue JS

How to ensure Vue.js code modularity by preventing prop mutation within a child component?

Footer flickers while changing routes

Troubleshooting Problem with NodeJS Https.request

Can you nest an if statement within another if statement within a return statement?

My REACT App is experiencing difficulties with routing