Exponentiation

Understand the efficiency and effectiveness of the exponentiation algorithm.

Naïve method

Given a number aa and a positive integer nn, suppose we want to compute ana^n. The standard naïve method is a simple for loop that performs n1n − 1 multiplications by aa:

Algorithm


SlowPower(a,n):xafor i2 to nxxareturn x\underline{SlowPower(a, n):} \\ \hspace{0.4cm} x←a \\ \hspace{0.4cm} for\space i ← 2 \space to\space n \\ \hspace{1cm} x←x·a \\ \hspace{0.4cm} return \space x

Implementation

import java.lang.*;
public class main {
public static int slowPower(int a, int n) {
int x = a;
for (int i = 2; i <= n; i++) {
x = x * a;
}
return x;
}
public static void main(String[] args) {
System.out.println("Answer is: " + slowPower(16, 2));
}
}
The slowPower method

Explanation

  • Line 4: This line defines a method named slowPower which takes two integers as input parameters a and n and returns an integer value.
  • Line 13: This line of code prints the result of the function slowPower with arguments 16 and 2.

Fast exponentiation algorithm

This iterative algorithm requires nn multiplications. The input parameter a could be an integer, a rational, or a floating point number. In fact, it doesn’t need to be a number at all as long as it’s something that we know how to multiply. For example, the same algorithm can be used to compute powers modulo some finite number (an operation commonly used in cryptography algorithms) or to compute powers of matrices (an operation used to evaluate recurrences and to compute shortest paths in graphs). Because we don’t know what kind of object we’re multiplying, we can’t know how much time a single multiplication requires, so we’re forced to analyze the running time in terms of the number of multiplications.

There is a much faster divide-and-conquer method, originally proposed by the Indian prosodist Pińgala in the 2nd century BCE, which uses the following simple recursive formula:

an={1 if n=0(an/2)2 if n > 0 and n is even(a[n/2])2.a otherwise a^n = \begin{cases} 1& \text{ if } n=0 \\ (a^{n/2})^2& \text{ if n > 0 and n is even} \\ (a^{[n/2]})^2.a& \text{ otherwise } \end{cases} ...

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy