Java language to implement fast exponentiation modulus algorithm in detail

The introduction of fast exponentiation modulus algorithm is proposed from the limitations of naive algorithm of large decimal modulus. In the naive method, we calculate a number, such as 5^1003%31, which consumes our computing resources very much. The most troublesome process in the whole calculation process is our 5^1003 process

Disadvantage 1: In the later calculation of the index, the calculated Numbers were not all increased, which occupied our computing resources (mainly time and space).

Drawback 2: The number of the intermediate process of our calculation is terrible. Our existing computers have no way to record such long data, so we have to come up with a more efficient way to solve this problem

When we calculate AB%C, the most convenient method is to call the pow method in Math function, but sometimes the number of A to the B power is too large, even the double precision double will overflow, at this time in order to get the result of AB%C, we will choose to use fast exponentiation algorithm, simple and fast to get the result we want.

To prevent number overflow and reduce complexity, we need to use the following formula:

ab mod c = (a mod c)b mod c

This formula means that the mod of the product is equal to the mod of the product. It is easy to see that this formula is transitive, so that we can make a smaller and smaller by constantly taking the remainder, preventing overflow.

Theoretically, with this formula, we can write code, by constantly taking a to ensure that the result does not overflow, it does calculate the larger power of the modulus, but this method is still O(N) complexity, is not fast.

In order to calculate the modulus of a power more quickly, we also rely on the following formula:

ab mod c = (a2)b/2 mod c, b is even
ab mod c = ((a2)b/2 · a) mod c, b odd

The formula is simple. The principle is to constantly replace b with a squared, and replace b with one half. Because we know from the first formula that the magnitude of one number to the same power is the same magnitude of one number. So we substitute a*a%c for a and the effect is one.

Therefore, according to the above formula, we can get the complexity O (logN) to calculate the fast power:

import java.util.Scanner;

public class Main {

 public static void main(String[] args) {
  Scanner in = new Scanner(System.in);
  int a = in.nextInt(), b = in.nextInt(), c = in.nextInt();
  int res = 1;
  a %= c;
  for (; b != 0; b /= 2) {
   if (b % 2 == 1)
    res = (res * a) % c;
   a = (a * a) % c;
  }
  System.out.println(res);
 }
}

This algorithm looks like this. The first step of a%=c is to reduce THE size of a by 1, so as to prevent the number overflow when a*a is performed the first time in for. In the loop of for, if b is odd, then make res=res*a, directly multiply a into the result, and finally do processing, in order to prevent the number overflow, directly operate the result of res*a mod c. Sooner or later, one day in the for loop, b will be equal to 1, enter the if branch, and finally calculate the value of res mod c exits the for loop to the final result.

conclusion

That's all for the detailed explanation of Java language fast exponentiation algorithm. I hope it will be helpful to you. Interested friends can continue to refer to other related topics in this site, if there is any deficiency, welcome to comment out. Thank you for your support!