JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Using Euclid's Algorithm | Reply
Re: Using Euclid's Algorithm (response to post by dimkadimon) | Reply
This is pretty much based on my Mathematics for Topcoders article, with a few minor modifications. I am sure there are many other problems that use this algorithm, but I couldn't find them.
Re: Using Euclid's Algorithm (response to post by dimkadimon) | Reply
Good. Would be even better to expand "Discussion" with the actual algorithm of solving Diophantine equations and examples of two problems solved using GCD.
Re: Using Euclid's Algorithm (response to post by Nickolas) | Reply
I can certainly give an algorithm for solving Diophantine equations, but I am not sure if I can do a good job at explaining the mathematics behind it. I don't want the cookbook to be too mathematical. What do you think?
Re: Using Euclid's Algorithm (response to post by dimkadimon) | Reply
It's Cookbook on programming, not on math, so I think it's fine just to describe the algorithm without its math background (maybe add a "See also" link to some place where it's explained in detail).
Re: Using Euclid's Algorithm (response to post by dimkadimon) | Reply
First of all, gcd can be written in one line:
int gcd(int a, int b) { return (b ? gcd(b, a%b) : abs(a)); }

This code works well for any signed integers except the pair (0, 0).

Second, I feel that this statement is wrong:
"Since the computational expense of each iteration has order h, the overall complexity grows as h^2."
Actually, each iteration requires division of h-digit numbers so it requires O(h^2) time instead of O(h). In this way you can only prove the overall O(h^3) complexity.
If the division is implemented in a proper way, it can be proved that the algorithm requires O(h^2) time. But the proof is rather difficult and not that obvious.
So let's change this statement just to "With proper division implementation the computational complexity for large numbers is O(h^2)" or something like that.

If we speak of large number gcd, we should include binary algorithm as it is much easier to implement for large numbers. Here is the code for ints:
int gcd(int a, int b) {
	if (a == 0) return b;
	if (b == 0) return a;
	if (a%2==0 && b%2==0) return gcd(a/2, b/2) * 2;
	else if (a%2 == 0) return gcd(a/2, b);
	else if (b%2 == 0) return gcd(a, b/2);
	else return (a>=b ? gcd(a-b, b) : gcd(a, b-a));
}

Works for nonnegative numbers only (except zero pair as always). Time is O(h^2).

I think we should make the extended Euclid algorithm clear:
int Euclid(int a, int b, int &x, int &y) {
	if (b == 0) {
		x = (a<0 ? -1 : 1);
		y = 0;
		return a*x;
	}
	int q = a/b;
	int r = a%b;
	int d = Euclid(b, r, y, x);
	y -= q*x;
	return d;
}
...
int x, y;
g = Euclid(a, b, x, y);

This code returns g = gcd(a, b) and also finds such x and y that:
a*x + b*y = g
It works for any pair of signed numbers (except zero pair). Moreover, the solution it finds is almost minimal in absolute value:
|x| <= |b|/g
|y| <= |a|/g
This experimental fact often allows us not to be afraid of overflow.

The solution for general diophantine equation includes a lot of cases such as a==0 or b==0 of c==0 plus signs of a and b etc. Do we really need to include it? The extended Euclid algorithm code is sufficient to find reciprocal element modulo M which is the most common usage.
Re: Using Euclid's Algorithm (response to post by syg96) | Reply
This code works well for any signed integers except the pair (0, 0).
What's wrong with the pair (0,0)? gcd(0,0) is 0.
Re: Using Euclid's Algorithm (response to post by MauricioC) | Reply
Yes, the algo will give zero. If you think it is correct, then the algorithm works for zero pair too=)
Speaking strictly mathematically, gcd(0, 0) is not defined. That's why I said it doesn't work for zero pair.
Re: Using Euclid's Algorithm (response to post by syg96) | Reply
Thank you for your input. Here are some comments:

* I avoided the one-line gcd() definition for clarity purposes.
* For the complexity I used the information from Wikipedia. Perhaps Wikipedia is wrong, or I misinterpreted.
* Thanks for the large number gcd. It will be nice to include it.
* I don't understand your extended euclid's algorithm, but I am happy to include it.
* I think my solution to diophantine equations should handle +/- of a and b. I am not sure that it deals with all 0 cases correctly. Please let me know if you find a bug in it. Personally, I feel that it is not necessary to include it, because it appears quite infrequently in problems.
Re: Using Euclid's Algorithm (response to post by dimkadimon) | Reply

Well, your gcd can return negative number on negative input. It can be a bad surprise for someone=) Better add "return abs(a);" or write a,b>=0 as input constraint or at least mention that your gcd can return negative result.

Wikipedia is right on complexity. And the proof about O(h^2) is correct there: it assumes that division is O(h(l+1)) and calculates the sum...


Well, I should have written the explanation of extended Euclid.
We want to find any solution (x, y) of equation:
a*x + b*y = gcd(a, b);

Two cases:
1. Let b == 0. Then
x = sgn(a); y = 0; is a solution:
a*sgn(a) + b*0 = a*sgn(a) = abs(a) = gcd(a, 0);
Moreover, we choose positive gcd here.
2. Let b != 0. Then
Divide a/b with reminder:
int q = a / b; (quotient)
int r = a % b; (reminder)
Then it is guaranteed (even for signed a,b !) that:
a = q*b + r;
Ok, now let's call Euclid(b, r, y, x) to solve the smaller problem recursively. It returns gcd(b, r) = gcd(a, b) and fills numbers y and x such that:
b*y + r*x = d (note that x and y are swapped)
Now use r = (a-q*b):
b*y + (a-q*b)*x = d
Now group everything around a and b:
d = b*y + (a-q*b)*x = b*y + a*x - q*b*x = a*x + b*(y-q*x)
This equation tells us that:
nx = x; ny = y - q*x; is a solution for problem a*nx + b*ny = gcd(a, b);
So the problem is solved.

In case I forget the formulas, I just write the equation for recursive call Euclid(b, a-q*b, recx, recy) on paper, group everything around a and b and get new solution.
The swapping of x and y is not necessary. It is just a hack which make code a bit shorter=)
So as soon as you understand this algorithm it is relatively easy to code.

About checking Diophantine code for all sorts of weird cases...=)
I made a training with such a problem. The absolute values of a, b, d are up to 10^9 there. You have to output any signed 32-bit integer solution.
If you want to check yourself, I can send you tests + checker over email (stgatilov@gmail.com)
Re: Using Euclid's Algorithm (response to post by dimkadimon) | Reply
syg96 was very kind and provided me with his code, as well as, some input/output data. Big thanks for that! I used this to find some small bugs in my code: overflowing int, not handling Math.abs(c)%gcd correctly when gcd==0. I fixed these bugs and now the code passes all tests and now I am 99% sure that it is correct. BTW I am now handling a==0, b==0 and c==0 as a special case.
RSS