Fast Exponentiation Power in Log N in DSA Typescript - Build from Scratch

Fast Exponentiation Power in Log N

📖 Scenario: Imagine you are building a calculator app that needs to quickly find the power of a number. Calculating powers by multiplying the base repeatedly can be slow for big numbers. Using fast exponentiation, you can find the power much faster, like a shortcut in math.

🎯 Goal: You will write a program in TypeScript that calculates base raised to the power exponent using fast exponentiation. This method works in O(log n) time, which means it is very fast even for large exponents.

📋 What You'll Learn

Create two variables: base and exponent with exact values 3 and 13 respectively.

Create a variable result initialized to 1 to hold the final answer.

Use a while loop to implement fast exponentiation logic using base, exponent, and result.

Print the final value of result after the loop ends.

💡 Why This Matters

🌍 Real World

Fast exponentiation is used in calculators, computer graphics, cryptography, and anywhere powers of numbers are needed quickly.

💼 Career

Understanding fast exponentiation helps in algorithm design, optimizing code, and working with encryption algorithms in software development.

1

Create base and exponent variables

Create a variable called base and set it to 3. Create another variable called exponent and set it to 13.

DSA Typescript

// Your code here

Hint

Use let to create variables and assign the exact numbers.

2

Initialize result variable

Create a variable called result and set it to 1. This will hold the final power value.

DSA Typescript

let base = 3;
let exponent = 13;
// Your code here

Hint

Start with 1 because multiplying by 1 does not change the value.

3

Implement fast exponentiation loop

Use a while loop that runs while exponent is greater than 0. Inside the loop, if exponent % 2 === 1, multiply result by base. Then square base by multiplying it by itself. Finally, divide exponent by 2 using integer division (use Math.floor).

DSA Typescript

let base = 3;
let exponent = 13;
let result = 1;
// Your code here

Hint

Remember to update result only when the exponent is odd, then square the base and halve the exponent.

4

Print the final result

Write console.log(result) to print the final power value after the loop.

DSA Typescript

let base = 3;
let exponent = 13;
let result = 1;

while (exponent > 0) {
    if (exponent % 2 === 1) {
        result *= base;
    }
    base *= base;
    exponent = Math.floor(exponent / 2);
}
// Your code here

Hint

The output should be the number 3 raised to the power 13.

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