On the eve of graduation, the ashes of the Computer School once again faced the scorching sun,
Go to an IT company to interview for the position of R&D engineer……
Half an hour later, the meeting room of the company, the interview begins……
Small gray writing, five minutes later……
Xiao Hui’s idea is very simple. He uses a brute force enumeration method to try to find a suitable integer I and see if it is divisible by both integer parameters numberA and numberB.
The integer I accumulates in a loop starting at 2 until it reaches half of the smaller arguments in numberA and numberB. At the end of the loop, the largest value of I found last time divisible by two numbers is the largest common divisor of the two numbers.
After the event, dejected small gray to consult with the department’s outstanding students rhubarb……
Toss and turn division, also known as Euclidean algorithm, is to find the greatest common divisor of two positive integers. It is the oldest known algorithm, dating back to 300 BC.
This algorithm is based on the theorem that two positive integers A and B (a>b) whose greatest common divisor is equal to the greatest common divisor between c and b of the remainder of a divided by B. Let’s say 10 and 25, 25 divided by 10 is 2 times more than 5, so the greatest common divisor of 10 and 25 is the same thing as the greatest common divisor of 10 and 5.
With this theorem, it’s easy to find the greatest common divisor. We can use recursion to simplify the problem step by step.
First, let’s calculate the remainder c of a divided by b, and convert the problem to finding the greatest common divisor of B and C; Then compute the remainder d of b divided by C, and turn the problem into finding the greatest common divisor of C and D; Then compute the remainder e of c divided by d, converting the problem to finding the greatest common divisor of d and e……
And so on, gradually reducing the operation between two larger integers to the operation between two smaller integers, until both numbers are divisible, or one of them is reduced to one.
Five minutes later, small gray changed the code……
The method of “more phase subtraction”, originated from the ancient Chinese Jiuzhang Suanshu, is also an algorithm for finding the greatest common divisor.
His principle was simpler: two positive integers A and B (a>b) whose greatest common divisor is equal to the difference c between A and B and the greatest common divisor of the smaller number B. Let’s say 10 and 25, 25 minus 10 is 15, so the greatest common divisor of 10 and 25 is the same thing as the greatest common divisor of 10 and 15.
From this, we can also simplify the problem recursively. First, we calculate the difference c between a and B (assuming a> B), and transform the problem into finding the greatest common divisor of B and C; Then calculate the difference d between C and B (assuming C > B), and transform the problem into finding the greatest common divisor of B and D; Then calculate the difference between B and D e (assuming b> D), and transform the problem into finding the greatest common divisor of d and e……
In the same way, the operation between two larger integers is gradually reduced to the operation between two smaller integers, until the two numbers can be equal, and the greatest common divisor is the two numbers that are eventually equal.
Five minutes later, Gray rewrites the code……
It is well known that the performance of shift operations is very fast. Given positive integers A and b, it is not difficult to reach the following conclusion. Where GCB (a,b) means the greatest common divisor function of a and B:
When a and b are even, GCB (a, b) = 2 * GCB (a / 2 b / 2) = 2 * GCB (a > > 1, b > > 1)
When a is even and b is odd, GCB (a,b) = GCB (a/2, b) = GCB (a>>1, b)
When a is odd and b is even, GCB (a,b) = GCB (a,b /2) = GCB (a,b >>1)
When both a and B are odd numbers, use the commutation detraction operation once, GCB (a,b) = GCB (b, a-b), then A-b must be even, and the shift operation can continue.
For example, the steps to calculate the greatest common divisor of 10 and 25 are as follows:
-
The integer 10 can be shifted to find the greatest common divisor of 5 and 25
-
Using the more phase reduction method, calculate 25-5=20, which is converted to find the greatest common divisor of 5 and 20
-
The integer 20 can be shifted to find the greatest common divisor of 5 and 10
-
The integer 10 can be shifted to find the greatest common divisor of 5 and 5
-
Using more phase reduction, since the two numbers are equal, the greatest common divisor is 5
When the two numbers are relatively small, the advantage of calculation times cannot be seen temporarily. When the two numbers are larger, the saving of calculation times is more obvious.
Finally, to summarize the time complexity of all the above solutions:
1. Violence enumeration method: time complexity is O(min(a, b))
2. Toss and turn division: the time complexity is not easy to calculate, which can be approximated to O(log(Max (a, b))), but the modulus operation performance is poor.
3. More phase reduction: avoids the modular operation, but the algorithm performance is unstable, the worst time complexity is O(Max (a, b)))
4. Combination of more phase reduction and shift: not only avoids modular operation, but also has stable algorithm performance and time complexity of O(log(Max (a, b)))
This article originally only wrote the division of tossing and turning on the end of the end, later users pointed out that there is a more optimized solution, it seems that they are uneducated, thank you very much for pointing out the problem. In addition, method parameters must be positive integers by default, so validation checks are omitted from the code.
The more phase reduction procedure described in this paper is a simplified approach. In the original text of The ninth Chapter on arithmetic, there is an extra step of verification: if both numbers are even, the two numbers will be halved before calculating the difference, so that the number of calculations will be less. This method achieves partial optimization, but the ancients seem not to have thought that even and odd cases can be optimized.
Due to the limitation of space, this paper omitted the principle and proof of the method of division and commutation. In fact, the proof process is not complicated, careful students can also try to study. Thank you for your support!
— — the END — — –
If you like this article, please long click the picture below to follow the subscription number programmer Xiao Grey and watch more exciting content
