Fast Exponentiation Power in Log N in DSA Javascript - Build from Scratch

Fast Exponentiation Power in Log N

📖 Scenario: Imagine you are building a calculator app that needs to quickly find the power of a number. Instead of multiplying the number many times, you want to use a faster way that works like splitting the work in half repeatedly.

🎯 Goal: You will create a function to calculate base raised to the power exponent using fast exponentiation. This method reduces the number of multiplications by using the idea of squaring and halving the exponent.

📋 What You'll Learn

Create two variables base and exponent with exact values 3 and 13 respectively.

Create a variable result and set it to 1 to hold the ongoing multiplication result.

Use a while loop that runs while exponent is greater than 0.

Inside the loop, if exponent is odd, multiply result by base.

Square the base and halve the exponent using integer division.

Print the final result after the loop ends.

💡 Why This Matters

🌍 Real World

Fast exponentiation is used in computer graphics, cryptography, and scientific calculations where powers of numbers need to be computed quickly.

💼 Career

Understanding efficient algorithms like fast exponentiation helps in optimizing code performance, which is valuable in software development and data science roles.

1

Create base and exponent variables

Create a variable called base and set it to 3. Create another variable called exponent and set it to 13.

DSA Javascript

# Your code here

Hint

Use const to create variables base and exponent with the exact values.

2

Create result variable

Create a variable called result and set it to 1. This will hold the multiplication result as you calculate the power.

DSA Javascript

const base = 3;
const exponent = 13;
# Your code here

Hint

Use let for result because it will change during the calculation.

3

Implement fast exponentiation loop

Create a variable called currentExponent and set it to exponent. Create a variable called currentBase and set it to base. Use a while loop that runs while currentExponent is greater than 0. Inside the loop, if currentExponent % 2 !== 0, multiply result by currentBase. Then square currentBase by multiplying it by itself. Finally, update currentExponent by dividing it by 2 and using Math.floor to keep it an integer.

DSA Javascript

const base = 3;
const exponent = 13;
let result = 1;
# Your code here

Hint

Use a while loop and check if the exponent is odd using % 2 !== 0. Multiply result by currentBase if odd. Then square currentBase and halve currentExponent using Math.floor.

4

Print the final result

Use console.log(result) to print the final value of result after the loop ends.

DSA Javascript

const base = 3;
const exponent = 13;
let result = 1;
let currentExponent = exponent;
let currentBase = base;

while (currentExponent > 0) {
    if (currentExponent % 2 !== 0) {
        result *= currentBase;
    }
    currentBase *= currentBase;
    currentExponent = Math.floor(currentExponent / 2);
}
# Your code here

Hint

Use console.log(result) to show the final answer.

Practice

1. What is the main advantage of using Fast Exponentiation to calculate baseexponent compared to simple repeated multiplication?

easy

A. It only works for exponents that are powers of two.

B. It uses less memory by storing all intermediate powers.

C. It avoids multiplication completely by using addition.

D. It reduces the number of multiplications from linear to logarithmic in the exponent.

Solution

1. Step 1: Understand simple repeated multiplication

   Calculating baseexponent by multiplying base by itself exponent times takes exponent multiplications, which is linear time.

2. Step 2: Understand fast exponentiation approach

   Fast exponentiation reduces multiplications by squaring results and halving the exponent, achieving logarithmic time complexity.

3. Final Answer:

   It reduces the number of multiplications from linear to logarithmic in the exponent. -> Option D

4. Quick Check:

   Fast exponentiation = fewer multiplications [OK]

Hint: Fast exponentiation halves exponent steps, speeding up power calculation [OK]

Common Mistakes:

• Thinking it avoids multiplication entirely
• Believing it only works for powers of two
• Confusing memory use with speed

2. Which of the following JavaScript function definitions correctly implements fast exponentiation for positive integers?

easy

A. function power(base, exp) { if (exp === 0) return 1; let half = power(base, Math.floor(exp / 2)); return exp % 2 === 0 ? half * half : half * half * base; }

B. function power(base, exp) { let result = 1; for (let i = 0; i < exp; i++) { result *= base; } return result; }

C. function power(base, exp) { return base ** exp; }

D. function power(base, exp) { if (exp === 1) return base; return power(base, exp - 1) * base; }

Solution

1. Step 1: Identify fast exponentiation pattern

   Fast exponentiation uses recursion with halving the exponent and squaring intermediate results.

2. Step 2: Check each function

   function power(base, exp) { if (exp === 0) return 1; let half = power(base, Math.floor(exp / 2)); return exp % 2 === 0 ? half * half : half * half * base; } uses recursion, halves the exponent, and squares results correctly. The other options use linear multiplication or built-in operator, not fast exponentiation.

3. Final Answer:

   implements fast exponentiation correctly. -> Option A

4. Quick Check:

   Recursion + halving exponent = fast exponentiation [OK]

Hint: Look for recursion with exponent halving and squaring [OK]

Common Mistakes:

• Choosing simple loops instead of recursion
• Using built-in power operator without algorithm
• Confusing base case conditions

3. What is the output of the following JavaScript code?

function fastPower(base, exp) {
  if (exp === 0) return 1;
  let half = fastPower(base, Math.floor(exp / 2));
  if (exp % 2 === 0) return half * half;
  else return half * half * base;
}
console.log(fastPower(2, 5));

medium

A. 32

B. 25

C. 16

D. 10

Solution

1. Step 1: Trace recursive calls for fastPower(2, 5)

   fastPower(2,5) calls fastPower(2,2), which calls fastPower(2,1), which calls fastPower(2,0)=1.

2. Step 2: Calculate values bottom-up

   fastPower(2,1) = 1*1*2 = 2; fastPower(2,2) = 2*2 = 4; fastPower(2,5) = 4*4*2 = 32.

3. Final Answer:

   32 -> Option A

4. Quick Check:

   2^5 = 32 [OK]

Hint: Trace recursion bottom-up, square halves, multiply base if odd [OK]

Common Mistakes:

• Calculating 2^5 as 16 by squaring only once
• Confusing exponent halving with division
• Missing multiplication by base when exponent is odd

4. The following code attempts to implement fast exponentiation but has a bug. What is the bug?

function fastPower(base, exp) {
  if (exp === 0) return 1;
  let half = fastPower(base, exp / 2);
  if (exp % 2 === 0) return half * half;
  else return half * half * base;
}

medium

A. The base case should return 0 instead of 1.

B. The exponent is not floored before recursive call, causing infinite recursion for odd exponents.

C. The multiplication order is incorrect for odd exponents.

D. The function does not handle negative exponents.

Solution

1. Step 1: Analyze recursive call argument

   The recursive call uses exp / 2 without flooring, so for odd exponents it passes a decimal, causing infinite recursion.

2. Step 2: Identify fix

   Using Math.floor(exp / 2) ensures the exponent decreases properly and recursion ends.

3. Final Answer:

   The exponent is not floored before recursive call, causing infinite recursion for odd exponents. -> Option B

4. Quick Check:

   Floor exponent before recursion to avoid infinite calls [OK]

Hint: Always floor exponent division in recursion [OK]

Common Mistakes:

• Ignoring decimal exponents in recursion
• Changing base case return value incorrectly
• Assuming multiplication order causes bugs

5. You want to compute 313 modulo 7 efficiently using fast exponentiation. Which of the following code snippets correctly implements this with modulo at each multiplication step to avoid large numbers?

hard

A. function modPower(base, exp, mod) {
if (exp === 0) return 0;
return (base * modPower(base, exp - 1, mod)) % mod;
}
console.log(modPower(3, 13, 7));

B. function modPower(base, exp, mod) {
let result = 1;
for (let i = 0; i < exp; i++) {
result = (result * base) % mod;
}
return result;
}
console.log(modPower(3, 13, 7));

C. function modPower(base, exp, mod) {
if (exp === 0) return 1;
let half = modPower(base, Math.floor(exp / 2), mod);
let halfSquared = (half * half) % mod;
if (exp % 2 === 0) return halfSquared;
else return (halfSquared * base) % mod;
}
console.log(modPower(3, 13, 7));

D. function modPower(base, exp, mod) {
return (base ** exp) % mod;
}
console.log(modPower(3, 13, 7));

Solution

1. Step 1: Understand modulo in fast exponentiation

   Modulo must be applied after each multiplication to keep numbers small and correct.

2. Step 2: Check each option

   function modPower(base, exp, mod) { if (exp === 0) return 1; let half = modPower(base, Math.floor(exp / 2), mod); let halfSquared = (half * half) % mod; if (exp % 2 === 0) return halfSquared; else return (halfSquared * base) % mod; } console.log(modPower(3, 13, 7)); applies modulo after squaring and multiplication recursively. function modPower(base, exp, mod) { let result = 1; for (let i = 0; i < exp; i++) { result = (result * base) % mod; } return result; } console.log(modPower(3, 13, 7)); uses linear loop (correct but slower). function modPower(base, exp, mod) { if (exp === 0) return 0; return (base * modPower(base, exp - 1, mod)) % mod; } console.log(modPower(3, 13, 7)); returns 0 for base case (wrong). function modPower(base, exp, mod) { return (base ** exp) % mod; } console.log(modPower(3, 13, 7)); uses built-in power without modulo at each step (incorrect for large exponents).

3. Final Answer:

   correctly implements fast exponentiation with modulo at each step. -> Option C

4. Quick Check:

   Modulo after each multiply keeps numbers small [OK]

Hint: Apply modulo after every multiplication step [OK]

Common Mistakes:

• Not applying modulo at intermediate steps
• Wrong base case returning 0
• Using built-in power without modulo