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

Fast Exponentiation Power in Log N

📖 Scenario: Imagine you are building a calculator that can quickly find the power of a number. Instead of multiplying the number many times, you want to use a faster way that works in steps, cutting down the work.

🎯 Goal: You will write a program in C that calculates base raised to the power exponent using fast exponentiation, which works in O(log n) time instead of O(n).

📋 What You'll Learn

Create two integer variables base and exponent with exact values 3 and 5

Create an integer variable result and set it to 1

Use a while loop with the condition exponent > 0

Inside the loop, use if (exponent % 2 == 1) to multiply result by base

Inside the loop, square base and divide exponent by 2 using integer division

Print the final value of result

💡 Why This Matters

🌍 Real World

Fast exponentiation is used in cryptography, computer graphics, and scientific calculations where powers of numbers must be computed quickly.

💼 Career

Understanding fast exponentiation helps in optimizing algorithms and is a common topic in coding interviews and software development roles.

1

Create base and exponent variables

Create two integer variables called base and exponent with values 3 and 5 respectively.

DSA C

// Create int variables base and exponent with values 3 and 5
// Your code here

Hint

Use int base = 3; and int exponent = 5; to create the variables.

2

Initialize result variable

Create an integer variable called result and set it to 1.

DSA C

int base = 3;
int exponent = 5;
// Create int variable result and set it to 1
// Your code here

Hint

Use int result = 1; to start the multiplication result.

3

Implement fast exponentiation loop

Use a while loop with the condition exponent > 0. Inside the loop, use if (exponent % 2 == 1) to multiply result by base. Then square base by multiplying it by itself, and divide exponent by 2 using integer division.

DSA C

int base = 3;
int exponent = 5;
int result = 1;
// Use while loop with condition exponent > 0
// Inside, if exponent % 2 == 1 multiply result by base
// Then square base and divide exponent by 2
// Your code here

Hint

Use a while loop and inside it check if exponent % 2 == 1 to multiply result by base. Then square base and halve exponent.

4

Print the final result

Print the value of result using printf with the format specifier %d.

DSA C

int base = 3;
int exponent = 5;
int result = 1;

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

Hint

Use printf("%d\n", result); to print the final answer.