GCD calculation — an error that is not noticed
What is the GCD, everyone knows from school. For those who have forgotten, I remind you: NOD is the greatest common divisor, dividing two integers without a remainder. For example, the GCD of the numbers 100 and 45 is 5, and the GCD of the numbers 17 and 7 is 1. There are several different search algorithms for this number. However, despite the fact that these are fairly simple algorithms, they often make one small, but very significant error.
I will consider 5 NOD calculation algorithms:
Naturally, the first option is often written - it is easy to remember, it is written quickly and works quite quickly.
Implementations work correctly on such tests:
Naturally, they will work on similar tests, where the arguments are non-negative integers. But what if ...
')
... if you replace one of the numbers with zero? For example:
The classical Euclidean algorithm (No. 3) already falls into an infinite loop.
By definition, a gcd can be defined for any two integers . So why not try tests, where one of the numbers is negative:
Everything becomes more interesting. The first two implementations give out a response of -5 . The third algorithm again falls into an infinite loop. Together with him in the infinite loop is the fifth algorithm. The fourth falls on StackOverFlow - most likely also falls into an infinite loop.
But the answer is -5 - wrong. By definition, GCD is the greatest common divisor. And such is the number 5 . After all, both the first and the second number are divided without a balance by 5. Hence, the first two implementations do not give the correct answer.
The Euclidean algorithm enters the loop due to the infinite increase in the arguments, if one of them is negative. Indeed, if you look at these lines, you can see that with a negative a (or b ), the subtraction operation is replaced by addition.
The same happens in the fourth and fifth algorithm:
In the situation when a or b are equal to 0 , then an infinite subtraction of zero occurs, which in no way changes the value of the arguments.
All of these algorithms are correct for input data, when both numbers a and b are non-negative integers. But let us remember once again - GCD exists for any two integers.
As arguments, the absolute value of numbers can be passed to the function, then the answer will be correct:
The second way to solve the problem is to return the absolute value of the answer:
The second option is much more preferable: less unnecessary calculations will be made than in the first option.
We considered five different options for calculating the greatest common divisor. For each of them, we indicated the input data on which the answer exists, but the solution “falls”, as well as the way to solve the problem.
Such small mistakes are most often made due to the fact that they do not notice the "slippery" places to solve a problem. Some of them are caught during the testing process, and some remain unnoticed.
In the situation with calculating GCD, almost all implementations are given with an error. On the web, I found only a couple of correctly working solutions, the rest are identical to those given at the beginning of the post.
Algorithms for computing GCD
I will consider 5 NOD calculation algorithms:
1. Recursion and residues
public static int gcd_1(int a, int b) { if (b == 0) return a; return gcd_1(b, a % b); } 2. The same remains, but without recursion
public static int gcd_2(int a, int b) { int t; while (b != 0) { t = b; b = a % b; a = t; } return a; } 3. Classic Euclidean Algorithm
public static int gcd_3(int a, int b) { while (a != b) { if (a > b) { a = a - b; } else { b = b - a; } } return a; } 4. Binary NOD search algorithm
public static int gcd_4(int a, int b) { if (a == b) return a; if (a == 0) return b; if (b == 0) return a; if ((~a & 1) != 0) { if ((b & 1) != 0) return gcd_4(a >> 1, b); else return gcd_4(a >> 1, b >> 1) << 1; } if ((~b & 1) != 0) return gcd_4(a, b >> 1); if (a > b) return gcd_4((a - b) >> 1, b); return gcd_4((b - a) >> 1, a); } 5. Binary algorithm based on bit arithmetic
public static int gcd_5(int a, int b) { int shift; if (a == 0) return b; if (b == 0) return a; for (shift = 0; ((a | b) & 1) == 0; ++shift) { a >>= 1; b >>= 1; } while ((a & 1) == 0) a >>= 1; do { while ((b & 1) == 0) b >>= 1; if (a > b) { int t = b; b = a; a = t; } b = b - a; } while (b != 0); return a << shift; } Naturally, the first option is often written - it is easy to remember, it is written quickly and works quite quickly.
Pretests
Implementations work correctly on such tests:
gcd(1, 10) = 1 gcd(5, 10) = 5 gcd(24, 24) = 24 gcd(0, 0) = 0 gcd(5,10) = 5
Naturally, they will work on similar tests, where the arguments are non-negative integers. But what if ...
')
The first tests with a trick
... if you replace one of the numbers with zero? For example:
gcd(5, 0) = 5 gcd(0, 15) = 15
The classical Euclidean algorithm (No. 3) already falls into an infinite loop.
Digging deeper
By definition, a gcd can be defined for any two integers . So why not try tests, where one of the numbers is negative:
gcd(-5,10) = ?
Everything becomes more interesting. The first two implementations give out a response of -5 . The third algorithm again falls into an infinite loop. Together with him in the infinite loop is the fifth algorithm. The fourth falls on StackOverFlow - most likely also falls into an infinite loop.
But the answer is -5 - wrong. By definition, GCD is the greatest common divisor. And such is the number 5 . After all, both the first and the second number are divided without a balance by 5. Hence, the first two implementations do not give the correct answer.
Why do solutions No. 3-5 go into an infinite loop?
The Euclidean algorithm enters the loop due to the infinite increase in the arguments, if one of them is negative. Indeed, if you look at these lines, you can see that with a negative a (or b ), the subtraction operation is replaced by addition.
if (a > b) { a = a - b; } else { b = b - a; }
The same happens in the fourth and fifth algorithm:
if (a > b) return gcd_4((a - b) >> 1, b); return gcd_4((b - a) >> 1, a);
if (a > b) { int t = b; b = a; a = t; } b = b - a;
In the situation when a or b are equal to 0 , then an infinite subtraction of zero occurs, which in no way changes the value of the arguments.
So what is wrong?
All of these algorithms are correct for input data, when both numbers a and b are non-negative integers. But let us remember once again - GCD exists for any two integers.
What to do?
As arguments, the absolute value of numbers can be passed to the function, then the answer will be correct:
int ans = gcd(Math.abs(a), Math.abs(b));
The second way to solve the problem is to return the absolute value of the answer:
public static int gcd(int a, int b) { if (b == 0) return Math.abs(a); return gcd(b, a % b); }
The second option is much more preferable: less unnecessary calculations will be made than in the first option.
Results
We considered five different options for calculating the greatest common divisor. For each of them, we indicated the input data on which the answer exists, but the solution “falls”, as well as the way to solve the problem.
Such small mistakes are most often made due to the fact that they do not notice the "slippery" places to solve a problem. Some of them are caught during the testing process, and some remain unnoticed.
In the situation with calculating GCD, almost all implementations are given with an error. On the web, I found only a couple of correctly working solutions, the rest are identical to those given at the beginning of the post.
Used literature, sources, implementations:
- Binary GCD algorithm - Wikipedia
- Euclidean algorithm - Wikipedia
- Euclidean algorithm - e-maxx
- Binary GCD - Dictionary of Algorithms and Data Structures
- Cormen - Algorithms - Construction and Analysis
Source: https://habr.com/ru/post/205106/
All Articles