Fast Exponentiation Power in Log N in DSA Javascript

Mental Model

We can find a number raised to a power quickly by breaking the problem into smaller parts and reusing results.

Analogy: Imagine climbing stairs two steps at a time instead of one. You reach the top faster by skipping steps smartly.

power(base, exponent)
  ↓
  base^exponent
  ↓
  base^(exponent/2) * base^(exponent/2) if exponent even
  or base * base^(exponent-1) if exponent odd

Dry Run Walkthrough

Input: Calculate 3^13 using fast exponentiation

Goal: Find 3 raised to the power 13 quickly using repeated squaring

Step 1: Check if exponent 13 is odd, multiply result by base 3 and reduce exponent to 12

result = 3, exponent = 12

Why: Odd exponent means we take one base out and handle the rest as even

Step 2: Square base: 3^2 = 9, halve exponent: 12 / 2 = 6

base = 9, exponent = 6, result = 3

Why: We reduce exponent by half to speed up calculation

Step 3: Exponent 6 is even, square base: 9^2 = 81, halve exponent: 6 / 2 = 3

base = 81, exponent = 3, result = 3

Why: Keep halving exponent and squaring base

Step 4: Exponent 3 is odd, multiply result by base: 3 * 81 = 243, reduce exponent to 2

result = 243, exponent = 2, base = 81

Why: Handle odd exponent by multiplying result by base

Step 5: Square base: 81^2 = 6561, halve exponent: 2 / 2 = 1

base = 6561, exponent = 1, result = 243

Why: Continue halving exponent and squaring base

Step 6: Exponent 1 is odd, multiply result by base: 243 * 6561 = 1594323, reduce exponent to 0

result = 1594323, exponent = 0, base = 6561

Why: Final odd exponent handled by multiplying result

Result:

Final result = 1594323

Annotated Code

DSA Javascript

class FastExponentiation {
  static power(base, exponent) {
    let result = 1;
    let currBase = base;
    let currExp = exponent;

    while (currExp > 0) {
      if (currExp % 2 === 1) {
        result *= currBase; // multiply result by base if exponent is odd
        currExp -= 1; // reduce exponent by 1 to make it even
      }
      currBase *= currBase; // square the base
      currExp = Math.floor(currExp / 2); // halve the exponent
    }

    return result;
  }
}

// Driver code
const base = 3;
const exponent = 13;
const output = FastExponentiation.power(base, exponent);
console.log(`${base}^${exponent} = ${output}`);

if (currExp % 2 === 1) {

check if exponent is odd to handle separately

result *= currBase; // multiply result by base if exponent is odd

multiply result by current base for odd exponent

currExp -= 1; // reduce exponent by 1 to make it even

make exponent even by subtracting one

currBase *= currBase; // square the base

square the base to prepare for halving exponent

currExp = Math.floor(currExp / 2); // halve the exponent

halve the exponent to reduce problem size

Output

3^13 = 1594323

Complexity Analysis

Time: O(log n) because the exponent is halved each step, reducing the number of multiplications

Space: O(1) because only a few variables are used regardless of exponent size

vs Alternative: Naive approach takes O(n) multiplications by multiplying base exponent times, which is slower for large exponents

Edge Cases

exponent = 0

returns 1 because any number to power 0 is 1

DSA Javascript

while (currExp > 0) {

exponent = 1

returns base itself as power 1 means base

DSA Javascript

while (currExp > 0) {

base = 0 and exponent > 0

returns 0 because zero to any positive power is zero

DSA Javascript

result *= currBase;

When to Use This Pattern

When you need to calculate large powers quickly, look for fast exponentiation using repeated squaring to reduce time from linear to logarithmic.

Common Mistakes

Mistake: Not handling odd exponents separately, causing incorrect results
Fix: Check if exponent is odd and multiply result by base before halving exponent

Mistake: Dividing exponent by 2 before handling odd case, losing one multiplication
Fix: First handle odd exponent by subtracting one, then halve exponent

Summary

Calculates base raised to exponent quickly by halving exponent and squaring base.

Use when you need to compute large powers efficiently without slow repeated multiplication.

The key is to break the problem into smaller powers by using exponent halving and handling odd exponents separately.

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