The introduction of a fast power modulus algorithm is proposed by the limitations of a naive algorithm that takes modulus from the decimals of large numbers. In the naive method, we calculate a number such as 5^1003%31, which consumes our computing resources very much. The most troublesome thing in the entire calculation process is our 5^1003 process.
Disadvantage 1: In the process of calculating the index later, the calculated numbers are not all increased, which takes up a lot of our computing resources (mainly time, and space)
Disadvantage 2: The numbers in our calculation are so big that our existing computers cannot record such long data, so we must think of a more efficient way to solve this problem.
When we calculate AB%C, the most convenient way is to call the pow method in the Math function. However, sometimes the number of A to the power of B is too large, and even double-precision double will overflow. At this time, in order to obtain the result of AB%C, we will choose to use the fast power modulus algorithm to obtain the result we want simply and quickly.
In order to prevent numbers from overflowing and reduce complexity, we need to use the following formula:
abmod c = (a mod c)bmod c
The meaning of this formula is: the product takes the remainder equal to the product takes the remainder. It is easy to see that this formula is transitive, so that we can make a smaller and smaller by constantly taking the remainder to prevent overflow.
Theoretically, with this formula, we can write code. By constantly moduloing a, we ensure that the result will not overflow. This can indeed calculate the modulus of a power to a larger power, but the complexity of this method is still O(N) and is not fast.
In order to calculate the modulus of a power more quickly, we also need to rely on the following formula:
ab mod c = (a2)b/2 mod c , b is an even number
ab mod c = ((a2)b/2・a) mod c , b is an odd number
This formula is very simple. The principle is to constantly replace b with the square of a and replace b with the original half. Because we know through the first formula that the module of a number has the same power (this sentence is a bit confusing, which means formula one). Then the effect of using the result of a*a%c instead of a is the same.
So according to the above formula, we obtain a method for calculating fast power with complexity O(logN):
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 is roughly like this. The first step is to reduce a%=c to prevent the number from overflowing when a*a is performed in for the first time. In the for loop, if b is an odd number, let res=res*a, and then multiply a into the result first, and then process it. In order to prevent the number from overflowing, the result mod c of res*a is directly operated. In this for loop, sooner or later, b will equal 1, enter the if branch, and finally calculate the value of res and mod c exits the for loop, and then the final result.
Summarize
The above is all the detailed explanation of this article on implementing the fast power modulus algorithm of Java language. I hope it will be helpful to everyone. Interested friends can continue to refer to other related topics on this site. If there are any shortcomings, please leave a message to point it out. Thank you friends for your support for this site!