1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
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

  1. Dec 22, 2017 #1

    s3a

    User Avatar

    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:
    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:
    SOLUTION OF PREVIOUS PROBLEM:
    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.:
    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) );
        }
    }
    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))!
     
  2. jcsd
  3. Dec 27, 2017 #2
    Thanks for the thread! This is an automated courtesy bump. Sorry you aren't generating responses at the moment. Do you have any further information, come to any new conclusions or is it possible to reword the post? The more details the better.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Loading...