C Program to Compute x^n — Binary Exponentiation O(log n)

Computing x raised to the power n (written xⁿ) naively requires n multiplications. Binary exponentiation (also called fast power or exponentiation by squaring) reduces this to O(log n) multiplications by halving the exponent at each step: if n is even, compute x^n/2 and square it; if n is odd, multiply x by x^n-1.

The original post used void main(), a function prototype declared inside main() (invalid in C89), and pow(power(x,n/2), 2) which unnecessarily converts the result to double. This rewrite uses a clean recursive implementation with long arithmetic and a correct n==0 base case.

Recursion Tree for 2¹⁰

Call	Action	Returns
power(2, 10)	even → half=power(2,5), return half*half	1024
power(2, 5)	odd → return 2 * power(2,4)	32
power(2, 4)	even → half=power(2,2), return half*half	16
power(2, 2)	even → half=power(2,1), return half*half	4
power(2, 1)	odd → return 2 * power(2,0)	2
power(2, 0)	base case → return 1	1

6 recursive calls for 2¹⁰ instead of 10 multiplications. For n=1000, this is 10 calls instead of 1000.

C Program: Compute x^n (Fast Exponentiation)

/* Compute x^n using fast recursive exponentiation (binary exponentiation)
 * Compile: gcc -ansi -Wall -Wextra xpown.c -o xpown */
#include <stdio.h>

/* Binary exponentiation: O(log n)
 * if n is even: x^n = (x^(n/2))^2
 * if n is odd:  x^n = x * x^(n-1)
 * base case:    x^0 = 1
 */
long power(long x, int n)
{
    long half;
    if (n == 0) return 1;
    if (n % 2 == 0) {
        half = power(x, n / 2);
        return half * half;   /* square the subresult */
    }
    return x * power(x, n - 1);
}

int main(void)
{
    long x;
    int n;

    printf("Enter x and n (x^n): ");
    if (scanf("%ld %d", &x, &n) != 2) {
        printf("Invalid input.\n");
        return 1;
    }
    if (n < 0) {
        printf("This program handles non-negative exponents only.\n");
        return 1;
    }

    printf("%ld ^ %d = %ld\n", x, n, power(x, n));
    return 0;
}

How to Compile and Run

gcc -ansi -Wall -Wextra xpown.c -o xpown
./xpown

Sample Output

Enter x and n (x^n): 2 10
2 ^ 10 = 1024

Enter x and n (x^n): 3 0
3 ^ 0 = 1

Enter x and n (x^n): 5 3
5 ^ 3 = 125

Code Explanation

Base case: n==0 returns 1 — any number raised to the power 0 equals 1 (by definition: the empty product). The original program had if (n==1) return x as its base case, which works for n≥1 but produces undefined behavior for n==0 — the recursion never terminates. Always include the n==0 base case.
Store half before squaring — the even branch does half = power(x, n/2); return half * half;. This is critical: if you wrote return power(x, n/2) * power(x, n/2); you would call the function twice, destroying the O(log n) performance and making it O(n) again. One call + one multiplication is correct.
The original used pow(power(x,n/2), 2) — this converts a long to double for the squaring operation. For large values of x^(n/2), double has only 15–17 significant digits of precision and may give the wrong integer result. Using integer multiplication avoids this problem.
Overflow note — long is typically 64 bits on 64-bit platforms (max ≈ 9.2×10¹⁸). For 2^62 = 4.6×10¹⁸ — near the limit. Larger values require arbitrary-precision arithmetic. For floating-point results, use pow() from <math.h> directly.

Naive vs Fast Exponentiation

Method	Multiplications for x^n	Example: x^1000
Naive loop	n − 1	999 multiplications
Binary exponentiation	≤ 2·log₂(n)	≤ 20 multiplications

What This Program Teaches

Divide and conquer — binary exponentiation is the canonical divide-and-conquer algorithm: split the problem in half, solve recursively, combine with one operation. The same pattern appears in merge sort, binary search, and Karatsuba multiplication.
Storing subresults — half = power(x, n/2); return half * half; avoids recomputing the recursive call. Failing to store the result (calling twice) converts O(log n) to O(n). This is one of the most common performance bugs in recursive programs.
Base case completeness — every valid input must eventually reach a base case. Here, n decreases on every branch (n→n/2 for even, n→n-1 for odd), and n==0 terminates. Missing the n==0 case causes infinite recursion for inputs that reduce to 0.

Related Programs

Practice what you learned: C Aptitude Questions — or try our C Programming Quiz App on Android.

C Program to Compute x^n — Fast Recursive Exponentiation