Fast Powering Algorithm
Algorithm · Core
Step through it: Divide & Conquer pattern
Step 1 of 6
Goal: sort [6, 3, 8, 2]. Big problems are hard and tiny ones are easy. Split in half until every piece is a single number (already sorted), then join the pieces back together in order.
Step 2 of 6
Split into [6, 3] and [8, 2].
Step 3 of 6
Split again until each piece is one number. One number is always sorted.
Step 4 of 6
Join neighbours in order: [6, 3] becomes [3, 6] and [8, 2] becomes [2, 8].
Step 5 of 6
Join the two sorted halves by repeatedly taking the smaller front number: 2, 3, 6, 8. There are about log n levels of splitting and each level handles every number once, so n log n. Solving halves and combining the answers is divide and conquer.
Step 6 of 6
Your turn.
Complexity
How to find a raised to the power b?
We multiply a to itself, b times. That
is, a^b = a * a * a * ... * a (b occurrences of a).
This operation will take O(n) time since we need to do multiplication operation
exactly n times.
The power of a number says how many times to use the number in a multiplication.
It is written as a small number to the right and above the base number.
Fast Power Algorithm
Can we do better than naive algorithm does? Yes we may solve the task of
powering in O(log(n)) time.
The algorithm uses divide and conquer approach to compute power. Currently the
algorithm work for two positive integers X and Y.
The idea behind the algorithm is based on the fact that:
For even Y:
X^Y = X^(Y/2) * X^(Y/2)For odd Y:
X^Y = X^(Y//2) * X^(Y//2) * X
where Y//2 is result of division of Y by 2 without reminder.For example
2^4 = (2 * 2) * (2 * 2) = (2^2) * (2^2)2^5 = (2 * 2) * (2 * 2) * 2 = (2^2) * (2^2) * (2)Now, since on each step we need to compute the same X^(Y/2) power twice we may optimise
it by saving it to some intermediate variable to avoid its duplicate calculation.
Time Complexity
Since each iteration we split the power by half then we will call function
recursively log(n) times. This the time complexity of the algorithm is reduced to:
O(log(n))Code
/**
* Fast Powering Algorithm.
* Recursive implementation to compute power.
*
* Complexity: log(n)
*
* @param {number} base - Number that will be raised to the power.
* @param {number} power - The power that number will be raised to.
* @return {number}
*/
export default function fastPowering(base, power) {
if (power === 0) {
// Anything that is raised to the power of zero is 1.
return 1;
}
if (power % 2 === 0) {
// If the power is even...
// we may recursively redefine the result via twice smaller powers:
// x^8 = x^4 * x^4.
const multiplier = fastPowering(base, power / 2);
return multiplier * multiplier;
}
// If the power is odd...
// we may recursively redefine the result via twice smaller powers:
// x^9 = x^4 * x^4 * x.
const multiplier = fastPowering(base, Math.floor(power / 2));
return multiplier * multiplier * base;
}References
Practice
Divide & Conquer
- Majority ElementEasy
- Convert Sorted Array to Binary Search TreeEasy
- Pow(x, n)Medium
- Sort ListMedium
- Maximum SubarrayMedium
- Different Ways to Add ParenthesesMedium
- Construct Quad TreeMedium
- Kth Largest Element in an ArrayMedium
- Merge k Sorted ListsHard
- Reverse PairsHard
- The Skyline ProblemHard
- Median of Two Sorted ArraysHard
Number Theory
- Greatest Common Divisor of StringsEasy
- Ugly NumberEasy
- Happy NumberEasy
- Plus OneEasy
- Add BinaryEasy
- Excel Sheet Column NumberEasy
- Count PrimesMedium
- Pow(x, n)Medium
- Factorial Trailing ZeroesMedium
- Ugly Number IIMedium
- Multiply StringsMedium
- Divide Two IntegersMedium
- Water and Jug ProblemMedium
- Super PowMedium
- Largest Component Size by Common FactorHard
Spotted a mistake or something unclear? Report it on GitHub.