Why Fast Exponentiation Power in Log N in DSA Typescript?

The Big Idea

Discover how to turn a long, tiring multiplication into a quick, clever trick!

The Scenario

Imagine you want to calculate a large power, like 2 raised to the 30th power, by multiplying 2 by itself 30 times manually.

This means doing 29 multiplications one after another, which takes a lot of time and effort.

The Problem

Doing repeated multiplication step-by-step is slow and tiring.

It also increases the chance of making mistakes in calculations.

For very large powers, this method becomes impractical and can take too long.

The Solution

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

It breaks the problem into smaller parts by squaring results and using the power's binary form.

This way, it calculates the power much faster, in about log base 2 of the power steps.

Before vs After

✗ Before

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

✓ After

function fastPower(base: number, exponent: number): number {
  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 makes it possible to calculate very large powers quickly and efficiently.

Real Life Example

Computers use fast exponentiation to quickly encrypt messages or calculate large numbers in science and engineering.

Key Takeaways

Manual repeated multiplication is slow and error-prone.

Fast Exponentiation reduces steps from n to about log n.

This makes power calculations fast and practical for big numbers.

Practice

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

easy

A. It reduces the time complexity from linear to logarithmic in terms of exponent.

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

C. It avoids using multiplication altogether.

D. It only works for small exponents.

Solution

1. Step 1: Understand simple exponentiation complexity

   Simple repeated multiplication calculates a^b by multiplying a by itself b times, which takes O(b) time.

2. Step 2: Analyze fast exponentiation complexity

   Fast exponentiation uses the idea of squaring and reduces the number of multiplications to O(log b), making it much faster for large exponents.

3. Final Answer:

   It reduces the time complexity from linear to logarithmic in terms of exponent. -> Option A

4. Quick Check:

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

Hint: Fast exponentiation halves exponent each step [OK]

Common Mistakes:

• Thinking it avoids multiplication
• Assuming it uses more memory
• Believing it only works for small exponents

2. Which of the following TypeScript function signatures correctly represents a fast exponentiation function for integers a and b?

easy

A. function fastPower(a: number): number

B. function fastPower(a: string, b: number): string

C. function fastPower(a: number, b: number): void

D. function fastPower(a: number, b: number): number

Solution

1. Step 1: Check parameter types

   The function needs two inputs: base a and exponent b, both numbers.

2. Step 2: Check return type

   The function returns the result of a^b, which is a number.

3. Final Answer:

   function fastPower(a: number, b: number): number -> Option D

4. Quick Check:

   Correct signature = function fastPower(a: number, b: number): number [OK]

Hint: Function needs two number inputs and returns number [OK]

Common Mistakes:

• Using string types for numbers
• Missing one parameter
• Returning void instead of number

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

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

medium

A. 25

B. 10

C. 32

D. 16

Solution

1. Step 1: Trace recursive calls for b=5

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

2. Step 2: Calculate results 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 C

4. Quick Check:

   2^5 = 32 [OK]

Hint: Remember 2^5 = 32, check recursive halving [OK]

Common Mistakes:

• Confusing multiplication order
• Forgetting to multiply by base when exponent is odd
• Incorrect base case handling

4. Identify the bug in this fast exponentiation function and select the correct fix:

function fastPower(a: number, b: number): number {
  if (b === 0) return 0;
  let half = fastPower(a, Math.floor(b / 2));
  if (b % 2 === 0) return half * half;
  else return half * half * a;
}

medium

A. Change recursive call to fastPower(a, b - 1)

B. Change base case return from 0 to 1

C. Remove the multiplication by 'a' when exponent is odd

D. Change Math.floor to Math.ceil in recursive call

Solution

1. Step 1: Check base case correctness

   When exponent is 0, a^0 should return 1, but code returns 0, which is incorrect.

2. Step 2: Identify fix for base case

   Changing return value in base case from 0 to 1 fixes the function to correctly compute powers.

3. Final Answer:

   Change base case return from 0 to 1 -> Option B

4. Quick Check:

   Base case must return 1 [OK]

Hint: Base case for exponent 0 must return 1 [OK]

Common Mistakes:

• Returning 0 for exponent 0
• Changing recursive call incorrectly
• Removing multiplication for odd exponent

5. You want to compute (3^13) % 7 efficiently using fast exponentiation with modulo to avoid large numbers. Which modification to the fastPower function is correct?

hard

A. Apply modulo after each multiplication: (half * half) % mod and (half * half * a) % mod

B. Apply modulo only once at the end of recursion

C. Apply modulo only to the base a before recursion

D. No modulo needed if exponent is small

Solution

1. Step 1: Understand modulo property in exponentiation

   To avoid large intermediate values, modulo must be applied after every multiplication step.

2. Step 2: Modify function to apply modulo after multiplications

   Applying modulo after half * half and half * half * a keeps numbers small and correct.

3. Final Answer:

   Apply modulo after each multiplication: (half * half) % mod and (half * half * a) % mod -> Option A

4. Quick Check:

   Modulo after each multiply keeps numbers small [OK]

Hint: Modulo after every multiply prevents overflow [OK]

Common Mistakes:

• Applying modulo only once at end
• Applying modulo only to base
• Ignoring modulo for small exponents