euclidean algorithm

[Fori Mix]

Hello! Can anyone help me to transform this code from python to java?

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

[Jesper de Jong]

Welcome to the Ranch.

Did you try writing this code in Java yourself? If yes, then please show us your Java code. Is there anything specific that you're having trouble with?

[Fori Mix]

Jesper de Jong wrote:Welcome to the Ranch.

Did you try writing this code in Java yourself? If yes, then please show us your Java code. Is there anything specific that you're having trouble with?

I am not really familiar with python. I understand that the line "g, y, x = egcd(b % a, a)" gives value to 3 variables (g,y,x) with one return command. I don't know how to do this in java and my biggest problem is the recursion. How can i give values to g, y and x in java?

[fred rosenberger]

Java does not allow you to return more than one value from a method.

So, your first step is to understand what the code above is doing. Not in terms of Java, not in terms of Python...but in English. Try describing the algorithm in words a 10-year old child could understand.

ONLY when you can do that should you consider writing a single line of Java.

[Steve Luke]

Fori Mix wrote:I understand that the line "g, y, x = egcd(b % a, a)" gives value to 3 variables (g,y,x) with one return command. I don't know how to do this in java and my biggest problem is the recursion. How can i give values to g, y and x in java?

Actually, that isn't really what the Python code is doing - Python, like Java, only returns a single value. Unlike Java, Python will automatically 'unpack' certain data types (Tuples) when it detects commas on the left side of the assignment.

So what egcd(a,b) does is return a datatype called a Tuple. A Tuple is like an array - it is a fixed size sequence. The sequence is unpacked so that the variables g, y, and x get the zeroth, first, and second value in the returned Tuple.

The key point to recognize a Tuple is the presence of Commas, though they usually are surrounded by parenthesis as well. The code has this return value:

return (g, x - (b // a) * y, y)

That is like saying this:

returnValue0 = g
returnValue1 = x - (b // a) * y
returnValue2 = y
return (returnValue0, returnValue1, returnValue2)

It is returning a Tuple of length 3 (a 3-tuple).