Is this implementation of gcd correct

Question

public static int divisor(int m, int n) {
    if (m == 0 || n == 0) {
        return m+n;
    } else {
        return divisor(n, m%n);
    }
}

It's giving me wrong answers for some input(I don't know which as they don't reveal which input they use for test case) in the amazon.interviewstreet.com

Also why this implementation keeps giving me stackoverflow(again no idea for which inputs)

public static int divisor(int m, int n) {
    if(m == 0 || n == 0) {
        return m+n;
    } else if (m > n) {
        return divisor(n, m%n);
    } else {
        return divisor(m, n%m);
    }
}

Please let me know what am I missing. I'm new to programming and am still a beginner.

Answer 1

I think first one is a code for a programming contest. If so be careful with your data types. May be 'int' is not enough to hold the inputs. Try 'long' instead. (and this will work only if your algorithm is correct.)

Answer 2

I think

return(m, n%m);

should be

return divisor(m, n%m);

Answer 3

Maybe invalid handling of negative values of n and m? Read e.g. this: Best way to make Java's modulus behave like it should with negative numbers?

Answer 4

for the second part what is

return(m, n%m);

Is this code get compiled ?

use :

public static int divisor(int m, int n) {
if(m == 0 || n == 0)
    return m+n;
else if(m>n)
    return divisor(n, m%n);
else
    return divisor(m, n%m);}

Answer 5

First,

return(m, n%m) 

definitely does not compile, I suppose it was meant to be

return divisor(m, n%m);

Second, I guess what is wrong in the second snippet is handling of negative numbers. Because A and B have the same GCD as -A and -B, I would add

m = Math.abs(m);
n = Math.abs(n);

to the beginning of the method

Answer 6

For the second part :

Also why this implementation keeps giving me stackoverflow(again no idea for which inputs)?

Try this input set :

5 3 1 16 5 10

It will give you the stackoverflow error. For your given code in pastebin.

Why ?

If the input is '1' there will be this problem.

edit your code part like below and see the out put for input (1 1).

public static int divisor(int m, int n) {
    System.out.println("### "+m+" "+n);
    if (m == 0 || n == 0) {
        return m + n;
    } else if (m > n) {
        return divisor(n, m % n);
    } else {
        return divisor(m, n % m);
    }
}

in some point out put will be like this :

.
.
### 1 1134903170
### 1 0
### 1 1836311903
### 1 0
### 1 -1323752223
### -1323752223 1
### -1323752223 1
### -1323752223 1
.
.

because in your code the function calling is like below.

   public static int divFib(int num) {
    int i = 1, j = 2, temp;

    while (divisor(num, j) == 1) {
        temp = j;
        j = j + i;
        i = temp;
    }
    return j;
   }

divisor(num, j) will be called like divisor(1, 2) then below part will execute

else {
        return divisor(m, n % m);
    }

the calling will be like divisor(1,0) because n%m = 2%1 =0

then '1' will be return as (m+n = 1).

then while (divisor(num, j) == 1){} will execute again and 'j' will be get increased. But 'num' is '1'. the same thing happens again and again. resulting 'j' to be a huge number and eventually it will assigned a negative number. (I think you know why its happening).

The thing is this will not ever stopped. so the stack will be overflowed due to huge number of function calls.

I think this is a quite clear explanation and if you have any doubt please ask. (Sorry i mistakenly post the answer here.)