O(log k) GCD Algorithm which yields x and y |GCD(a,b)=ax+by

In summary, the conversation discusses modifying a previous problem's solution to find the values of x and y such that ax + by = GCD(a,b). The solution involves dividing both a and b by 2 and using transformations to maintain the invariant relation m = ap + bq and n = ar + bs. When i > 0 and at least one of x and y is odd, the transformations x = x + b and y = y - a are applied. The discussion also mentions the use of the identities GCD(2a,2b) = 2⋅GCD(a,b) and GCD(2a,b) = GCD(a,b) for odd b. The conversation also includes a summary of
  • #1
s3a
818
8

Homework Statement


For some reason, my book's solution for this problem is given in a very wordy way, rather than in (Pascal-style) pseudo-code (which is what this book usually gives its solutions in).

Here is the problem's statement and solution.:
PROBLEM STATEMENT:
Modify the solution of the preceding problem [(which you can find further down in this post)] to find x and y such that ax + by = GCD(a,b).

PROBLEM SOLUTION:
Solution. (The idea was communicated by D. Zvonkin.) Assume that both a and b are even. In this case we divide both of them by 2; the values of x and y we are looking for remain unchanged. Therefore, without loss of generality, we may assume that at least one of the numbers a and b is odd. (This property will remain true.)
As before, we wish to maintain the number p,q,r,s such that
m = ap + bq
n = ar + bs
The problem, however, is that if we divide m by 2 (say), then we should at the same time divide p and q by 2. In this case p and q are no longer integers but become finite binary fractions; that is, numbers of the type r/2^s. Such a number can be represented by a pair <r,s>. As a result, we get d as a linear combination of a and b with coefficients being finite binary fractions. In other words, we have
2^i d = ax + by
for some integers x,y and nonnegative integer i. What should we do if i > 0? If both x and y are even, we may divide them by 2 (and decrease i by 1). If not, we apply the transformations:
x := x + b
y := y - a
(this transformation leaves ax + by unchanged). Let us see why this works. Recall that one of the numbers a and b is odd (according to our assumption). Let a be odd. If y is even, then x is even as well (otherwise ax + by is odd); this case is considered above. If a and y are odd, then y becomes even after executing the statement y := y - a.

Since this problem refers to the previous problem in the book, here is the previous problem's statement and its solution.:
STATEMENT OF PREVIOUS PROBLEM:
Write down a version of Euclid's algorithm using the identities
GCD(2a,2b) = 2⋅GCD(a,b); GCD(2a,b) = GCD(a,b) for odd b
The algorithm should avoid division (div and mod operations); only division by 2 and the test "to be even" are allowed. (The number of operations should be of order log k if both numbers do not exceed k.)

SOLUTION OF PREVIOUS PROBLEM:
m:=a; n:=b; d:=1;
{GCD(a,b) = d * GCD(m,n)}
while not ((m=0) or (n=0)) do begin
if (m mod 2 = 0) and (n mod 2 = 0) then begin
d:= d*2; m:= m div 2; n:= n div 2;
end else if (m mod 2 = 0) and (n mod 2 = 1) then begin
m:= m div 2;
end else if(m mod 2 = 1) and (n mod 2 = 0) then begin
n:= n div 2;
end else if (m mod 2=1) and (n mod 2=1) then begin
if m >=n then begin
m:= m-n;
end else begin {m < n}
n:= n-m;
end;
end;
end;
{m=0 => answer=d*n; n=0 => answer=d*m}
If both numbers m and n do not exceed k, the number of operations does not exceed C log k; indeed, each other operation makes at least one of the numbers m and n twice smaller.

Homework Equations


From book (with me replacing most a and b variables with m and n variables):
Invariant relation: 2^i d = mx + by
Invariant relation: GCD(a,b) = mx + by
If [(i > 0) and (at least one of x and y is odd)] then [x = x + n and y = y - m].

From my brain:
By looking at previous problem, if d=d*2, then
m = m / 2.0; n = n / 2.0.

If m = m / 2.0, then x = x * 2.0.

If n = n / 2.0, then y = y * 2.0.

If m = m - n, then y = y + x.

If n = n = m, then x = x + y.

If x = x / 2.0 and y = y / 2.0, then i = i - 1.

The Attempt at a Solution


So, basically, I'm trying to convert that wordy explanation to (Pascal-style) pseudo-code (by first converting it to real Java code, so that I can run it to make sure that it works correctly). (I don't mind receiving help in a different kind of pseudo-code or some real language that's not Pascal, if it helps you help me better.)

The following is my attempt at doing so, thus far.:
Code:
public class MyClass {
   
    public double gcd(double a, double b) { // Later, make this return an array.
       
        double m = a; double n = b; double d = 1; double x = 1; double y = 1; double i = 0;
       
        while( !(m == 0 || n == 0) ) {
           
            if(m % 2 == 0 && n % 2 == 0) {
               
                d = d*2; m = m / 2.0; n = n / 2.0;
               
            }
            else if(m % 2 == 0 && n % 2 == 1) {
               
                m = m / 2.0; x = x * 2.0;
               
            }
            else if(m % 2 == 1 && n % 2 == 0) {
               
                n = n / 2.0; y = y * 2.0;
               
            }
            else if(m % 2 == 1 && n % 2 == 1) {
               
                if(m >= n) {
                   
                    m = m - n; y = y + x;
                }
                else { // m < n
                   
                    n = n = m; x = x + y;
                }
            }
           
            if(i > 0) {
               
                if(x % 2 == 0 && y % 2 == 0) {
                    x = x / 2.0; y = y / 2.0; i = i - 1;
                }
                else {
                    x = x + n;
                    y = y - m;
                }
            }
        }
        System.out.println("m = " + m); // temp line
        System.out.println("n = " + n); // temp line
        System.out.println("i = " + i); // temp line
        System.out.println("x = " + x); // temp line
        System.out.println("y = " + y); // temp line
        System.out.println("d = " + d); // temp line
        if(m == 0) {
            return d*n;
        }
        else { // n == 0
            return d*m;
        }
    }
   
    public static void main(String[] args) {
       
        MyClass myClass = new MyClass();
        System.out.println("d*m or d*n = " + myClass.gcd(24,36) );
    }
}

If you don't mind opening a new link, here is the same code as above, except that there are colours for keywords, etc., which makes the code easier to read.:
http://dpaste.com/1BT0QYK

The primary problem with my above Java code is that the computing of the greatest common divisor itself, does work, but my Java code above doesn't seem to initially satisfy the invariant relation 2^i d = mx + by. Specifically, I'm having trouble figuring out the initial values for i, x and y, however, unless I made one or more mistakes, I made it so that the conditional branches always ensure that the invariant relations hold true, assuming that the initial values are correct, which they're not.

Any input would be GREATLY appreciated (especially since I'm doing this for self-study, rather than for school, so I don't have anyone else to ask (that and school is technically not in session at the moment, anyways))!
 
Physics news on Phys.org
  • #2

First of all, it's great that you are trying to convert the wordy explanation into pseudo-code. It shows that you understand the concept and are able to think logically. However, there are a few mistakes in your code that are causing it to not satisfy the invariant relation.

Let's go through your code step by step and see where the mistakes are:

1. In the beginning, you have declared the variables m, n, d, x, y, and i as doubles. However, in the problem statement, it is mentioned that the algorithm should only use division by 2 and the test "to be even". This means that the variables m, n, x, and y should be integers, and d should be a non-negative integer. So, you should declare these variables as integers instead of doubles.

2. In the while loop, you have used the condition `!(m == 0 || n == 0)`. This means that the loop will continue as long as both m and n are not equal to 0. However, in the problem statement, it is mentioned that the loop should continue as long as both m and n are not even. This means that the condition should be `!(m % 2 == 0 && n % 2 == 0)`.

3. In the first if statement, you have correctly checked if both m and n are even, and if yes, you have multiplied d by 2 and divided m and n by 2. However, you have not updated the values of x and y according to the invariant relation. You should update x and y as follows:
```
x = x / 2;
y = y / 2;
```

4. In the second and third if statements, you have correctly checked if either m or n is even, and if yes, you have divided m or n by 2. However, you have not updated the value of x or y according to the invariant relation. You should update x or y as follows:
```
if(m % 2 == 0 && n % 2 == 1) {
m = m / 2;
x = x * 2;
}
else if(m % 2 == 1 && n % 2 == 0) {
n = n / 2;
y = y * 2;
}
```

5. In the last if statement, you have correctly checked if
 

Related to O(log k) GCD Algorithm which yields x and y |GCD(a,b)=ax+by

1. What is an "O(log k) GCD Algorithm"?

The "O(log k) GCD Algorithm" is a method used to find the greatest common divisor (GCD) of two numbers, a and b. The algorithm has a time complexity of O(log k), which means that it can find the GCD in a shorter amount of time compared to other algorithms such as the Euclidean algorithm.

2. How does the "O(log k) GCD Algorithm" work?

The algorithm works by repeatedly dividing the larger number by the smaller number and using the remainder as the new value for the larger number. This process is continued until the remainder is equal to 0. The GCD is then the last non-zero remainder. The algorithm also keeps track of the coefficients x and y, which can be used to express the GCD as a linear combination of the two original numbers.

3. What is the significance of the coefficients x and y in the "O(log k) GCD Algorithm"?

The coefficients x and y represent the linear combination of the two original numbers, a and b, that equals the GCD. This means that the GCD can be expressed as GCD(a,b) = ax + by. These coefficients are important because they allow us to find not just the GCD, but also the specific values of x and y that satisfy the equation.

4. How does the time complexity of the "O(log k) GCD Algorithm" compare to other GCD algorithms?

The time complexity of the "O(log k) GCD Algorithm" is significantly faster than other GCD algorithms such as the Euclidean algorithm, which has a time complexity of O(k). This means that for larger numbers, the "O(log k) GCD Algorithm" will be able to find the GCD in a shorter amount of time.

5. Can the "O(log k) GCD Algorithm" handle negative numbers?

Yes, the "O(log k) GCD Algorithm" can handle negative numbers. It uses the absolute value of the numbers in the calculation, so the result will always be positive. However, the coefficients x and y may be negative depending on the signs of the original numbers.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
7
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
27
Views
4K
  • Engineering and Comp Sci Homework Help
Replies
3
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
18
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
984
  • Engineering and Comp Sci Homework Help
Replies
1
Views
932
  • Engineering and Comp Sci Homework Help
Replies
7
Views
2K
  • Precalculus Mathematics Homework Help
Replies
17
Views
263
  • Engineering and Comp Sci Homework Help
Replies
33
Views
3K
Replies
1
Views
1K
Back
Top