Calculating Large Exponents

[jkmyoung]

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.println("7 to the 13th power = " + pow(7,13));
where exp >= 1

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;
}

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:

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;
}

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...

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;
}

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:

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;
}

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:

long pow(long n, long exp){
  prod = 1;
  while (exp > 0){
    if ((exp & 1) != 0)
       prod *= n;
    n*=n;
    exp >>= 1;
  }
  return prod;
}

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:

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;
}

See the YouTube demonstration of this method

Number of Multiplications
Same as method 4: At most 2 log2(exp)

************************************************** *******
Difference in number of multiplications

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
 

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^30234922 % 3293527 or
928020^329010455 % 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,

[himmu7]

Thank U so much for ur explanations

[Motoma]

This is great! Thanks for sharing.