Exponentiation
Understand the efficiency and effectiveness of the exponentiation algorithm.
Naïve method
Given a number and a positive integer , suppose we want to compute . The standard naïve method is a simple for
loop that performs multiplications by :
Algorithm
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));}}
Explanation
- Line 4: This line defines a method named
slowPower
which takes two integers as input parametersa
andn
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 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:
...
Create a free account to access the full course.
By signing up, you agree to Educative's Terms of Service and Privacy Policy