(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

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:

PROBLEM SOLUTION: 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).

Since this problem refers to the previous problem in the book, here is the previous problem's statement and its 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.

STATEMENT OF PREVIOUS PROBLEM:

SOLUTION 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.)

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.2. Relevant 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.

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

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.:Code (Text):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) );

}

}

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 Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

Have something to add?

Draft saved
Draft deleted

**Physics Forums | Science Articles, Homework Help, Discussion**