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

[s3a]

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.:

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))!

 

[KataKoniK]

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