Fast Exponentiation Power in Log N in DSA C# - 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, until exponent reaches zero.

Execution Sample

DSA C#

int Power(int baseVal, int exp) {
  if (exp == 0) return 1;
  int half = Power(baseVal, exp / 2);
  if (exp % 2 == 0) return half * half;
  else return half * half * baseVal;
}

Calculates base raised to exp using recursion, reducing exponent by half each call for efficiency.

Execution Table

Step	Operation	Exponent	Recursive Call Result	Calculation	Return Value
1	Power(2, 10) called	10	-	-	-
2	Check exp==0?	10	-	No	-
3	Recursive call Power(2, 5)	5	-	-	-
4	Check exp==0?	5	-	No	-
5	Recursive call Power(2, 2)	2	-	-	-
6	Check exp==0?	2	-	No	-
7	Recursive call Power(2, 1)	1	-	-	-
8	Check exp==0?	1	-	No	-
9	Recursive call Power(2, 0)	0	-	-	-
10	Check exp==0?	0	-	Yes	1
11	Return 1 to Power(2,1)	1	1	exp odd: 1*1*2	2
12	Return 2 to Power(2,2)	2	2	exp even: 2*2	4
13	Return 4 to Power(2,5)	5	4	exp odd: 4*4*2	32
14	Return 32 to Power(2,10)	10	32	exp even: 32*32	1024

💡 Exponent reaches 0 at step 10, recursion unwinds returning final result 1024

Variable Tracker

Variable	Start	After Step 10	After Step 11	After Step 12	After Step 13	After Step 14
exp	10	0 (step 10)	1 (step 11)	2 (step 12)	5 (step 13)	10 (step 14)
half (recursive result)	-	1	1	2	4	32
return value	-	1	2	4	32	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, so we multiply once more by base to compensate, as shown in steps 11 and 13.

Why does the recursion stop when exponent is zero?

Because any number to the power 0 is 1, so step 10 returns 1 to end recursion.

How does halving the exponent reduce the number of recursive calls?

Each recursive call halves the exponent, so the depth of recursion is logarithmic in exponent size, making it efficient as seen by steps 3, 5, 7, 9.

Visual Quiz - 3 Questions

Look at the execution table, what is the return value at step 11?

A 2

B 1

C 4

D 32

💡 Hint

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

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

A Step 9

B Step 11

C Step 10

D Step 12

💡 Hint

Look at the 'Exponent' and 'Operation' columns to find when exp == 0.

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

A It would be 1024

B It would be 512

C It would be 256

D It would be 2048

💡 Hint

Recall that 2^9 = 512, so final return value changes accordingly.

Concept Snapshot

Fast Exponentiation (Power in Log N):
- Use recursion to halve exponent each call
- Base case: exponent == 0 returns 1
- If exponent even: result = half * half
- If exponent odd: result = half * half * base
- Runs in O(log n) time, efficient for large exponents

Full Transcript

Fast exponentiation calculates power by reducing the exponent quickly. It checks if exponent is zero, returning 1. Otherwise, it calls itself with half the exponent. If exponent is even, it squares the half result. If odd, it multiplies the square by base once more. This reduces recursive calls to logarithmic count, making it efficient. The execution table shows each recursive call and return, with values tracked step-by-step.

Practice

1. What is the main advantage of using Fast Exponentiation Power in Log N over the simple repeated multiplication method?

easy

A. It works only for positive exponents

B. It uses less memory by storing all intermediate powers

C. It reduces the time complexity from linear to logarithmic

D. It avoids multiplication altogether

Solution

1. Step 1: Understand the time complexity of simple exponentiation

   Simple repeated multiplication multiplies the base by itself n times, which takes O(n) time.

2. Step 2: Understand the time complexity of fast exponentiation

   Fast exponentiation uses squaring and reduces the number of multiplications to about O(log n).

3. Final Answer:

   It reduces the time complexity from linear to logarithmic -> Option C

4. Quick Check:

   Fast exponentiation = O(log n) time [OK]

Hint: Remember: halve the exponent each step for log speed [OK]

Common Mistakes:

• Thinking it avoids multiplication
• Assuming it only works for positive exponents
• Confusing memory usage with speed

2. Which of the following C# code snippets correctly implements the fast exponentiation method to compute pow(base, exponent)?

easy

A. int FastPow(int baseVal, int exp) { int result = 1; while (exp > 0) { if ((exp & 1) == 1) result *= baseVal; baseVal *= baseVal; exp >>= 1; } return result; }

B. int FastPow(int baseVal, int exp) { int result = 0; for (int i = 0; i < exp; i++) result += baseVal; return result; }

C. int FastPow(int baseVal, int exp) { if (exp == 0) return 0; return baseVal * FastPow(baseVal, exp - 1); }

D. int FastPow(int baseVal, int exp) { int result = 1; for (int i = 0; i < exp; i++) result *= baseVal; return result; }

Solution

1. Step 1: Analyze the code for fast exponentiation logic

   int FastPow(int baseVal, int exp) { int result = 1; while (exp > 0) { if ((exp & 1) == 1) result *= baseVal; baseVal *= baseVal; exp >>= 1; } return result; } uses bitwise operations to check odd exponent and squares base, which is the fast exponentiation method.

2. Step 2: Check other options for correctness

   int FastPow(int baseVal, int exp) { int result = 0; for (int i = 0; i < exp; i++) result += baseVal; return result; } adds baseVal repeatedly (wrong for power), C returns 0 for exp=0 (should be 1), D uses simple loop (not fast).

3. Final Answer:

   int FastPow(int baseVal, int exp) { int result = 1; while (exp > 0) { if ((exp & 1) == 1) result *= baseVal; baseVal *= baseVal; exp >>= 1; } return result; } -> Option A

4. Quick Check:

   Bitwise & squaring = fast exponentiation [OK]

Hint: Look for bitwise checks and squaring in code [OK]

Common Mistakes:

• Using addition instead of multiplication
• Returning 0 for exponent 0
• Using simple loops instead of bitwise

3. What is the output of the following C# code snippet?

int FastPow(int baseVal, int exp) {
    int result = 1;
    while (exp > 0) {
        if ((exp & 1) == 1) result *= baseVal;
        baseVal *= baseVal;
        exp >>= 1;
    }
    return result;
}

Console.WriteLine(FastPow(3, 4));

medium

A. 81

B. 64

C. 27

D. 12

Solution

1. Step 1: Trace the fast exponentiation for base=3, exp=4

   exp=4 (100b): - exp even, skip multiply, base=3*3=9, exp=2 - exp=2 (10b): even, skip multiply, base=9*9=81, exp=1 - exp=1 (1b): odd, multiply result=1*81=81, base=81*81=6561, exp=0 Loop ends.

2. Step 2: Final result is 81

   The function returns 81, which is 3^4.

3. Final Answer:

   81 -> Option A

4. Quick Check:

   3^4 = 81 [OK]

Hint: Remember to square base and halve exponent each step [OK]

Common Mistakes:

• Multiplying when exponent bit is zero
• Not updating base correctly
• Confusing exponent bits

4. Identify the bug in the following fast exponentiation code and select the correct fix:

int FastPow(int baseVal, int exp) {
    int result = 1;
    while (exp > 0) {
        if ((exp & 1) == 1) result *= baseVal;
        baseVal *= baseVal;
        exp = exp / 2;
    }
    return result;
}

medium

A. Replace exp = exp / 2; with exp >>= 1; for efficiency

B. Change multiplication to addition in result *= baseVal;

C. Initialize result to 0 instead of 1

D. Add a check for negative exponent at start

Solution

1. Step 1: Analyze the code for handling negative exponents

   The code does not handle negative exponents, since while (exp > 0) skips the loop and returns 1, which is wrong.

2. Step 2: Identify the fix

   Adding a check for negative exponent and handling it (e.g., returning 0 or using reciprocal) is necessary.

3. Final Answer:

   Add a check for negative exponent at start -> Option D

4. Quick Check:

   Negative exponent needs special handling [OK]

Hint: Always check for negative exponents before loop [OK]

Common Mistakes:

• Ignoring negative exponents
• Changing result initialization incorrectly
• Replacing division with bit shift without understanding

5. You want to compute pow(base, exponent) modulo m efficiently using fast exponentiation. Which modification should you make to the standard fast exponentiation algorithm to handle large numbers and avoid overflow?

hard

A. Use floating point arithmetic instead of integers

B. Apply modulo m after every multiplication step

C. Only apply modulo m at the end of the computation

D. Increase the size of integer variables to long long

Solution

1. Step 1: Understand overflow risk in large exponentiation

   Multiplying large numbers repeatedly can cause integer overflow before final modulo.

2. Step 2: Apply modulo at each multiplication

   Taking modulo after every multiplication keeps intermediate results small and prevents overflow.

3. Final Answer:

   Apply modulo m after every multiplication step -> Option B

4. Quick Check:

   Modulo after each multiply avoids overflow [OK]

Hint: Modulo after each multiply keeps numbers small [OK]

Common Mistakes:

• Applying modulo only once at end
• Using floating point causing precision loss
• Ignoring overflow risk