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