Fast Exponentiation Power in Log N in DSA Javascript - Execution Trace

Concept Flow - Fast Exponentiation Power in Log N

Start with base and exponent

↓

Is exponent 0?

Yes→Return 1

No↓

Is exponent even?

Yes→Square base, halve exponent

↓

Recursive call with new base and exponent

↓

Multiply result by base

↓

Return result

This flow shows how the exponent is reduced by half each step if even, or multiplied by base if odd, to compute power efficiently.

Execution Sample

DSA Javascript

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

Computes base raised to exp using recursion and halving exponent for fast calculation.

Execution Table

Step	Operation	Exponent	Recursive Call	Return Value	Visual State
1	Call power(2, 10)	10	power(2,5)	pending	Start with base=2, exp=10
2	Call power(2, 5)	5	power(2,2)	pending	Exp is odd, will multiply by base later
3	Call power(2, 2)	2	power(2,1)	pending	Exp is even, square result of half
4	Call power(2, 1)	1	power(2,0)	pending	Exp is odd, multiply by base later
5	Call power(2, 0)	0	None	1	Base case reached, return 1
6	Return from power(2, 0)	0	None	1	Return 1 to power(2,1)
7	Calculate power(2,1)	1	None	2	half=1, odd exp: 1*1*2=2
8	Return from power(2,1)	1	None	2	Return 2 to power(2,2)
9	Calculate power(2,2)	2	None	4	half=2, even exp: 2*2=4
10	Return from power(2,2)	2	None	4	Return 4 to power(2,5)
11	Calculate power(2,5)	5	None	32	half=4, odd exp: 4*4*2=32
12	Return from power(2,5)	5	None	32	Return 32 to power(2,10)
13	Calculate power(2,10)	10	None	1024	half=32, even exp: 32*32=1024
14	Return from power(2,10)	10	None	1024	Final result returned

💡 Recursion ends when exponent reaches 0, returning 1 as base case.

Variable Tracker

Variable	Start	After Step 5	After Step 7	After Step 9	After Step 11	After Step 13	Final
exp	10	0	1	2	5	10	10
half (return value)	N/A	1	1	2	4	32	32
result	N/A	N/A	2	4	32	1024	1024

Key Moments - 3 Insights

Why do we multiply by base only when exponent is odd?

Because when exponent is odd, after halving it loses one factor of base. Multiplying by base restores that factor, as shown in steps 7 and 11 in the execution_table.

Why does the recursion stop at exponent 0 and return 1?

Exponent 0 means any number to power 0 is 1. This is the base case stopping recursion, as seen in step 5 where power(2,0) returns 1.

How does halving the exponent reduce the number of multiplications?

Halving exponent reduces problem size by half each call, so total calls are about log2(exp). This is why steps go from 10 to 5 to 2 to 1, reducing multiplications drastically.

Visual Quiz - 3 Questions

Look at the execution_table, what is the return value of power(2,1) at step 7?

A 1

B 4

C 2

D 32

💡 Hint

Check the 'Return Value' column at step 7 in execution_table.

At which step does the exponent become zero, ending recursion?

A Step 6

B Step 5

C Step 10

D Step 14

💡 Hint

Look for the step where 'Exponent' is 0 in execution_table.

If the exponent was 9 instead of 10, how would the final return value at step 14 change?

A It would be 512

B It would be 1024

C It would be 2048

D It would be 256

💡 Hint

Recall 2^9 = 512, check final return value logic in execution_table step 14.

Concept Snapshot

Fast Exponentiation (Power) in Log N:
- Use recursion to halve exponent each call
- Base case: exp=0 returns 1
- If exp even: result = power(base, exp/2)^2
- If exp odd: result = power(base, floor(exp/2))^2 * base
- Reduces multiplications from N to log N
- Efficient for large exponents

Full Transcript

Fast exponentiation calculates base raised to an exponent quickly by reducing the exponent by half each recursive call. When the exponent is zero, it returns 1 as the base case. If the exponent is even, it squares the result of the recursive call with half the exponent. If odd, it multiplies that squared result by the base once more. This method reduces the number of multiplications from linear to logarithmic in the exponent size, making it very efficient for large powers.

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