Calculating Large Exponents
Background: This is a quick article as to how to calculate the exponents of large numbers quickly and efficiently.
Starting with a basic multiplication algorithm, it gives subsequently faster algorithms and a few quick examples.
The techniques used in this article can be used in general mathematics, encryption, among other things.
In this article, the following conventions are used:
^ operator is to mean exponent, not the bitwise xor operation. So 2^3 is 2 cubed = 2 * 2 * 2.
* is multiplication
% is mod is modular division. Eg 10 mod 3 ≡ 1.
log2 stands for log base 2.
How do we calculate exponents? n^exp
*************** *************** *************** ************
Method 1: Simple Method
The first way we learn to calculate exponents is the expand and multiply out scenario. Let's take 7^13 as an example:
7^13 = 7*7*7*7*7*7*7*7 *7*7*7*7*7
7 * 7 = 49
49 * 7 = 343
343 * 7 = 2401
2401 * 7 = 16807
16807 * 7 = 117649
117649 * 7 = 823543
823543 * 7 = 5764801
5764801 * 7 = 40353607
40353607 * 7 = 282475249
282475249 * 7 = 1977326743
1977326743 * 7 = 13841287201
13841287201 * 7 = 96889010407
Codewise: Note in order to be concise, we'll set the following framework for all of the code in this article:
We create a power function:
long pow(long n, long exp);
Example of calling the function:
System.out.prin tln("7 to the 13th power = " + pow(7,13));
where exp >= 1
Although this works with small exponents, for larger exponents, it's quite a bit of work. Surely there must be a better way.
Number of multiplications :
exp - 1
*************** *************** *************** ************
Method 2: Divide and Conquer
Property of exponents:
if c = a + b
n^a * n^b = n^c
Applying to our example, we could have:
13 = 6 + 7
So 7^13 = 7^6 * 7^7!
7 * 7 = 49 = 7^2
49 * 7 = 343 = 7^3
343 * 7 = 2401 = 7^4
2401 * 7 = 16807 = 7^5
16807 * 7 = 117649 = 7^6
117649 * 7 = 823543 = 7^7
117649 * 823543 = 96889010407 = 7^6 * 7^7 = 7^13
Codewise, this might look like:
prod eventually equals 7^6 and prod2 is set to 7^7.
Number of multiplications :
Calculating the base values: (exp / 2) - 1 + (exp % 2)
Final multiplication: 1
Total: (exp / 2) + (exp % 2)
This time, we have only 7 multiplications ! (vs 12 earlier). Can we do better?
*************** *************** *************** ************
Method 3: Divide more and conquer
We can improve on this divide and conquer method even more! Divide 13 into more than 2 parts. Since 3^2 < 13 < 4^2,
and 3*4 < 13, divide it into 4 parts:
13 = 3 + 3 + 3 + 4
7^13 = 7^3 * 7^3 * 7^3 * 7^4
7 * 7 = 49 = 7^2
49 * 7 = 343 = 7^3
343 * 7 = 2401 = 7^4
343 * 343 = 117649 = 7^3*7^3 = 7^6
117649 * 343 = 40353607 = 7^6*7^3 = 7^9
40353607 * 2401 = 96889010407 = 7^9*7^4 = 7^13
The code for this part is a little tricky, so skip over it if it's too hard to understand. The hard part is figuring out how many parts you need.
Som examples of dividing the exponent into parts:
exp = 10, 10: 3, 3, 4
exp = 11, 11: 3, 4, 4
exp = 12, 12: 3, 3, 3, 3 (chosen this way as opposed to 4,4,4. Easier to code)
exp = 13, 13: 3, 3, 3, 4
exp = 14, 14: 3, 3, 4, 4
exp = 15, 15: 3, 4, 4, 4
etc...
Number of multiplications :
Calculating the base values: rounddown sqrt(n) (-1 if n is square)
Multiplying the base values together: round sqrt(n+0.25) - 1
Total multiplications : about 2 * sqrt(n)
6 multiplications !
*************** *************** *************** ************
Method 4: Binary exponents (2^k-ary method)
Now we've still been using method 1 to calculate the first parts of our calculation, which is slow. With this method, we do away with it altogether.
Take the binary of 13. 13 = 1101 in binary, or 8 + 4 + (0)*2 + 1 = 8 + 4 + 1
Now we calculate 7^1, 7^2, 7^4, 7^8.
7 = 7^1
7 * 7 = 49 = 7^1 * 7^1 = 7^2
49 * 49 = 2401 = 7^2 * 7^2 = 7^4
2401 * 2401 = 5764801 = 7^4 * 7^4 = 7^8
Now that we've calculated 7 to the power of a power of 2, note that 7^13 = 7^8 * 7^4 * 7^1
5764801 * 2401 = 13841287201 = 7^8 * 7^4 = 7^12
13841287201 * 7 = 96889010407 = 7^12 * 7 = 7^13
Codewise:
4b: Calculate as you go.
Notice that we're storing 7^1, 7^2, 7^4, 7^8. With this method, you don't have to store that extra space; we multiply as we go. Have 2 numbers, product and current. Product will calculate our temporary product, while current will calculate the powers of (powers of 2).
current = 7
13 is odd, so product = 7
current = 7*7 = 49 = 7^2
13's 2nd bit is not set, so product stays at 7.
current = 49 * 49 = 2401 = 7^4
13's 3rd bit is set, so product = 7 * 2401 = 16807 = 7 * 7^4 = 7^5
current = 2401 * 2401 = 5764801 = 7^8
13's 4th bit is set, so product = 16807 * 5764801 = 96889010407 = 7^5 * 7^8 = 7^13
Codewise:
5 multiplications with this example.
However, keep in mind that this is with a small exponent (13). If calculating a large exponent, say 1000, it would take only about 20 multiplications ! (Compared with at least 60 in the other methods)
Number of multiplications :
Calculating 7^2^log2(exp) : log2(exp)
Calculating the product : log2(exp) at most
Total: 2 * log2(exp)
Method 5. Sliding Window method:
This is an efficient variant of the (2^k-ary) method.
13 = 1101 in binary.
So we take the first digit: 1, then the first 2: 11, the first 3:110, and finally the whole sequence: 1101
7 = 7^1 ~ 1 in binary
Square it:
7 * 7 = 49 = 7^2 ~ 10 in binary.
49 * 7 = 343 = 7^3 ~ 11 in binary.
Square it:
343 * 343 = 117649 = 7^6 ~ 110 in binary.
Square it:
117649 * 117649 = 13841287201 = 7^12 ~ 1100 in binary
13841287201 * 7 = 96889010407 = 7^13 ~ 1101 in binary
Notice when we square a number, it's the same as adding a 0 to the end of the binary.
If the exponent has a 0 at the end, we can change the last digit to a 1 by multiplying by the number.
The code:
See the YouTube demonstration of this method
Number of Multiplications
Same as method 4: At most 2 log2(exp)
*************** *************** *************** ************
Difference in number of multiplications
Look at the difference once we start getting into the millions. If your exponents are even bigger, you can see the difference it'll make!
Hopefully these tips will help you out when you have to calculate numbers like
30249327^302349 22 % 3293527 or
928020^32901045 5 % 781323
Good luck!
Extra notes:
There are many other methods for calculating large exponents, but these are probably the first few basic ones. Of course, if your numbers are bigger than longs, than you can substitute your own BigInt classes.
If using these methods modularly, you can calculate the mod of each result, and the results will still apply. (Eg, if you're using this in a Riemann encryption scheme.)
Links:
Wikipedia
YouTube demonstration of method 5
Tags:
Powers, exponents, mod, encryption, large numbers,
Background: This is a quick article as to how to calculate the exponents of large numbers quickly and efficiently.
Starting with a basic multiplication algorithm, it gives subsequently faster algorithms and a few quick examples.
The techniques used in this article can be used in general mathematics, encryption, among other things.
In this article, the following conventions are used:
^ operator is to mean exponent, not the bitwise xor operation. So 2^3 is 2 cubed = 2 * 2 * 2.
* is multiplication
% is mod is modular division. Eg 10 mod 3 ≡ 1.
log2 stands for log base 2.
How do we calculate exponents? n^exp
*************** *************** *************** ************
Method 1: Simple Method
The first way we learn to calculate exponents is the expand and multiply out scenario. Let's take 7^13 as an example:
7^13 = 7*7*7*7*7*7*7*7 *7*7*7*7*7
7 * 7 = 49
49 * 7 = 343
343 * 7 = 2401
2401 * 7 = 16807
16807 * 7 = 117649
117649 * 7 = 823543
823543 * 7 = 5764801
5764801 * 7 = 40353607
40353607 * 7 = 282475249
282475249 * 7 = 1977326743
1977326743 * 7 = 13841287201
13841287201 * 7 = 96889010407
Codewise: Note in order to be concise, we'll set the following framework for all of the code in this article:
We create a power function:
long pow(long n, long exp);
Example of calling the function:
System.out.prin tln("7 to the 13th power = " + pow(7,13));
where exp >= 1
Code:
long pow(long n, long exp){
long power, prod;
prod = n; // hold the product of our multiplication.
for (power = 2; power <= exp; power ++)
{
prod *= n; // prod = n^power
}
return prod;
}
Number of multiplications :
exp - 1
*************** *************** *************** ************
Method 2: Divide and Conquer
Property of exponents:
if c = a + b
n^a * n^b = n^c
Applying to our example, we could have:
13 = 6 + 7
So 7^13 = 7^6 * 7^7!
7 * 7 = 49 = 7^2
49 * 7 = 343 = 7^3
343 * 7 = 2401 = 7^4
2401 * 7 = 16807 = 7^5
16807 * 7 = 117649 = 7^6
117649 * 7 = 823543 = 7^7
117649 * 823543 = 96889010407 = 7^6 * 7^7 = 7^13
Codewise, this might look like:
Code:
long pow(long n, long exp){
long halfexp = exp / 2;
long power, prod, prod2;
prod = n; // hold the product of our multiplication.
for (power = 2; power <= halfexp; power ++)
{
prod *= n; //prod = n^power
}
if (exp % 2 == 0)
prod2 = prod;
else
prod2 = prod *n;
return prod * prod2;
}
Number of multiplications :
Calculating the base values: (exp / 2) - 1 + (exp % 2)
Final multiplication: 1
Total: (exp / 2) + (exp % 2)
This time, we have only 7 multiplications ! (vs 12 earlier). Can we do better?
*************** *************** *************** ************
Method 3: Divide more and conquer
We can improve on this divide and conquer method even more! Divide 13 into more than 2 parts. Since 3^2 < 13 < 4^2,
and 3*4 < 13, divide it into 4 parts:
13 = 3 + 3 + 3 + 4
7^13 = 7^3 * 7^3 * 7^3 * 7^4
7 * 7 = 49 = 7^2
49 * 7 = 343 = 7^3
343 * 7 = 2401 = 7^4
343 * 343 = 117649 = 7^3*7^3 = 7^6
117649 * 343 = 40353607 = 7^6*7^3 = 7^9
40353607 * 2401 = 96889010407 = 7^9*7^4 = 7^13
The code for this part is a little tricky, so skip over it if it's too hard to understand. The hard part is figuring out how many parts you need.
Som examples of dividing the exponent into parts:
exp = 10, 10: 3, 3, 4
exp = 11, 11: 3, 4, 4
exp = 12, 12: 3, 3, 3, 3 (chosen this way as opposed to 4,4,4. Easier to code)
exp = 13, 13: 3, 3, 3, 4
exp = 14, 14: 3, 3, 4, 4
exp = 15, 15: 3, 4, 4, 4
etc...
Code:
long pow(long n, long exp){
long sqroot = (long)(Math.sqrt(exp)); // truncates answer
long parts; // number of terms we need
long power; // current power
long prod; // to hold n^sqrt(exp)
long prod2; // to hold n^(sqrt(exp) + 1)
long prod3; // final answer
long terms; // number of terms remaining to be multiplied
prod = n; // hold the product of our multiplication.
for (power = 2; power <= sqroot; power ++)
{
prod *= n; //prod = n^power
}
if (exp == sqroot * sqroot) // perfect square!
prod2 = prod;
else {
prod2 = prod * n;
parts = sqroot;
if (exp >= sqroot * (sqroot + 1)){
parts++;
}
prod3 = prod; // initialize our final answer. Work backwards for a little simplicity.
//joined for loops.
for (terms = parts - 1; terms > exp % parts; terms--){
prod3 *= prod;
}
for (;terms > 0; terms--){
prod3 *= prod2;
}
return prod3;
}
Calculating the base values: rounddown sqrt(n) (-1 if n is square)
Multiplying the base values together: round sqrt(n+0.25) - 1
Total multiplications : about 2 * sqrt(n)
6 multiplications !
*************** *************** *************** ************
Method 4: Binary exponents (2^k-ary method)
Now we've still been using method 1 to calculate the first parts of our calculation, which is slow. With this method, we do away with it altogether.
Take the binary of 13. 13 = 1101 in binary, or 8 + 4 + (0)*2 + 1 = 8 + 4 + 1
Now we calculate 7^1, 7^2, 7^4, 7^8.
7 = 7^1
7 * 7 = 49 = 7^1 * 7^1 = 7^2
49 * 49 = 2401 = 7^2 * 7^2 = 7^4
2401 * 2401 = 5764801 = 7^4 * 7^4 = 7^8
Now that we've calculated 7 to the power of a power of 2, note that 7^13 = 7^8 * 7^4 * 7^1
5764801 * 2401 = 13841287201 = 7^8 * 7^4 = 7^12
13841287201 * 7 = 96889010407 = 7^12 * 7 = 7^13
Codewise:
Code:
long pow(long n, long exp){
Vector<long> powers;
long exp2 = exp; // copy of exp
long prod = n; // holds n^2^index;
long prod2 = 1;
while (exp2 > 0){
powers.add(n);
exp2 >>= 1; // right shift 1.
prod *= prod;
}
int power = 1; // n^(2^power)
while(exp > 0){
if ((exp & 1) != 0){ // 1 bit set
prod *= powers[power];
}
power++;
exp >>= 1;
}
return prod;
}
Notice that we're storing 7^1, 7^2, 7^4, 7^8. With this method, you don't have to store that extra space; we multiply as we go. Have 2 numbers, product and current. Product will calculate our temporary product, while current will calculate the powers of (powers of 2).
current = 7
13 is odd, so product = 7
current = 7*7 = 49 = 7^2
13's 2nd bit is not set, so product stays at 7.
current = 49 * 49 = 2401 = 7^4
13's 3rd bit is set, so product = 7 * 2401 = 16807 = 7 * 7^4 = 7^5
current = 2401 * 2401 = 5764801 = 7^8
13's 4th bit is set, so product = 16807 * 5764801 = 96889010407 = 7^5 * 7^8 = 7^13
Codewise:
Code:
long pow(long n, long exp){
prod = 1;
while (exp > 0){
if ((exp & 1) != 0)
prod *= n;
n*=n;
exp >>= 1;
}
return prod;
}
However, keep in mind that this is with a small exponent (13). If calculating a large exponent, say 1000, it would take only about 20 multiplications ! (Compared with at least 60 in the other methods)
Number of multiplications :
Calculating 7^2^log2(exp) : log2(exp)
Calculating the product : log2(exp) at most
Total: 2 * log2(exp)
Method 5. Sliding Window method:
This is an efficient variant of the (2^k-ary) method.
13 = 1101 in binary.
So we take the first digit: 1, then the first 2: 11, the first 3:110, and finally the whole sequence: 1101
7 = 7^1 ~ 1 in binary
Square it:
7 * 7 = 49 = 7^2 ~ 10 in binary.
49 * 7 = 343 = 7^3 ~ 11 in binary.
Square it:
343 * 343 = 117649 = 7^6 ~ 110 in binary.
Square it:
117649 * 117649 = 13841287201 = 7^12 ~ 1100 in binary
13841287201 * 7 = 96889010407 = 7^13 ~ 1101 in binary
Notice when we square a number, it's the same as adding a 0 to the end of the binary.
If the exponent has a 0 at the end, we can change the last digit to a 1 by multiplying by the number.
The code:
Code:
long pow(long n, long exp){
long multBit = Long.HighestSetBit(exp); //used to keep track of where we are in exponent, starting at highest bit.
long prod = n;
for (multBit >>= 1; // ignore the first 1.
multBit > 0;
multBit >>=1)
{
prod *= prod;
if ((multBit & exp) != 0)
prod *= n;
}
return prod;
}
Number of Multiplications
Same as method 4: At most 2 log2(exp)
*************** *************** *************** ************
Difference in number of multiplications
Code:
Method 1 2 3 4 exp O(n) O(n/2) O(sqrt(n)) O(log(n)) 2 1 1 1 1 3 2 2 2 2 4 3 2 2 3 5 4 3 3 3 10 9 5 5 5 25 24 13 9 6 100 99 50 19 8 250 249 125 31 9 1000 999 500 62 11 2500 2499 1250 99 13 10000 9999 5000 199 15 25000 24999 12500 315 16 100000 99999 50000 631 18 250000 249999 125000 999 19 1000000 999999 500000 1999 21
Hopefully these tips will help you out when you have to calculate numbers like
30249327^302349 22 % 3293527 or
928020^32901045 5 % 781323
Good luck!
Extra notes:
There are many other methods for calculating large exponents, but these are probably the first few basic ones. Of course, if your numbers are bigger than longs, than you can substitute your own BigInt classes.
If using these methods modularly, you can calculate the mod of each result, and the results will still apply. (Eg, if you're using this in a Riemann encryption scheme.)
Links:
Wikipedia
YouTube demonstration of method 5
Tags:
Powers, exponents, mod, encryption, large numbers,
Comment