Detailed explanation of fast power modulus algorithm implemented in Java language

The introduction of fast power modulus algorithm is proposed by the limitations of the simple algorithm of taking modulus from decimals of large numbers. In the simple method, we calculate a number, such as 5 ^ 1003% 31, which consumes our computing resources very much. In the whole calculation process, the most troublesome is our 5 ^ 1003 process

Disadvantage 1: in the process of calculating the index later, the calculated numbers do not increase, which takes up our computing resources (mainly time and space)

Disadvantage 2: the intermediate process of our calculation is terrible. Our existing computers can't 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 method is to call the pow method in the math function. However, sometimes the b-power number of a is too large, and even the double precision will overflow. At this time, in order to get the result of AB% C, we will choose to use the fast power modulus algorithm to get the result we want simply and quickly.

In order to prevent digital 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 remainder of the product is equal to the remainder of the product of the remainder. It is easy to see that this formula is transitive, so we can make a smaller and smaller by constantly taking remainder to prevent overflow.

Theoretically, with this formula, we can write code. By constantly taking the modulus of a, we can ensure that the result will not overflow. This can indeed calculate the modulus of the power of the larger power, but the complexity of this method is still o (n), which is not fast.

In order to calculate the modulus of power more quickly, we also need to 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 is odd

This formula is very simple. The principle is to constantly replace B with the square of a and replace B with half of the original. Because we know through the first formula that the modules of a number to the same power are the same (this sentence is a bit around, which means Formula 1). Then we use the result of a * a% C instead of a, the effect is the same.

Therefore, according to the above formula, we get a fast power calculation method such as complexity O (logn):

This algorithm is about the same. The first step of a% = C is to reduce a and prevent the number overflow when a * a is performed for the first time in for. In the for loop, if B is an odd number, let res = res * a, directly multiply a into the result, and finally handle it. In order to prevent digital overflow, directly operate the result mod C of res * a. In this for loop, sooner or later, 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.

summary

The above is all about the detailed explanation of the fast power modulus algorithm in Java language. I hope it will be helpful to you. Interested friends can continue to refer to other related topics on this site. If there are deficiencies, please leave a message to point out. Thank you for your support!