Why Fast Exponentiation Power in Log N in DSA Javascript?

The Big Idea

What if you could calculate huge powers in seconds instead of minutes?

The Scenario

Imagine you want to calculate a large power like 2³⁰ by multiplying 2 by itself 30 times manually.

Doing this step-by-step is slow and tiring, especially if the number is huge.

The Problem

Multiplying the base repeatedly for every power takes a lot of time and effort.

It is easy to make mistakes counting multiplications or lose track.

This slow method wastes time and computer resources.

The Solution

Fast Exponentiation uses a smart way to reduce the number of multiplications.

It breaks the problem into smaller parts and reuses results, cutting the work from N steps to about log N steps.

This makes calculating big powers quick and efficient.

Before vs After

✗ Before

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

✓ After

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

What It Enables

This method enables fast calculation of very large powers, making complex math and algorithms practical.

Real Life Example

Fast Exponentiation is used in computer security to quickly compute large powers for encryption and decryption.

Key Takeaways

Manual repeated multiplication is slow and error-prone.

Fast Exponentiation reduces steps from N to log N by dividing the problem.

This technique is essential for efficient computations in many fields.

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