How can I only use 2 variables in Java as with the Python code?

Question

Can this Python code also be written in Java code? :

def gcd(a, b):
    # Return greatest common divisor using Euclid's Algorithm.
    while b:
        a, b = b, a % b
    return a

print (gcd(210, 45))

This is what I've so far in Java code:

private static int gcd(int p, int q) {
    // Return greatest common divisor using Euclid's Algorithm.
    int temp;
    while (q != 0) {
        temp = q;
        q = p % q;
        p = temp;
    }
    return p;
}

System.out.println(gcd(210, 45));

As you can see the Java code uses 3 variables whereas the Python code only uses 2 variables. I also want to use only 2 variables in the Java code and I want to keep the while loop and I don't want to use recursion.

Also why does Java need 1 more variable than the Python code? Except for the fact that the Python code uses a tuple.

Java doesn't have syntactic sugar for parallel assignment, so you need a temporary holding variable to do the multiple assignments sequentially without losing info. — pjs, Jul 31 '20 at 20:34
Ok I was wrong, it uses the stack directly to swap the elements out: https://stackoverflow.com/questions/21047524/how-does-swapping-of-members-in-tuples-a-b-b-a-work-internally — Dici, Jul 31 '20 at 20:37
Well... you COULD use a little bit of trickery like so: `a = a %b; a += b; b = a - b; a -= b;` — Turing85, Jul 31 '20 at 20:39
@Dici That's actually cool. I always assumed it used a temp variable and had never looked under the hood at it. Good comment! — Rashid 'Lee' Ibrahim, Jul 31 '20 at 20:39
@pjs the overflow caused by the addition is reversed by the substraction. — Turing85, Jul 31 '20 at 20:44
@Dici Well, but how is *that* implemented? Looks like [with *two* temporary variables](https://github.com/python/cpython/blob/cadda52d974937069eeebea1cca4229e2bd400df/Python/ceval.c#L1534-L1538). — superb rain, Jul 31 '20 at 20:46
@Turing85 It's been years since I had to write any Java so I don't have a JVM lying around to check - have you actually tried that to confirm that overflow can be reversed by subtraction? XOR is guaranteed to not overflow in the first place. — pjs, Jul 31 '20 at 20:50
@superbrain ah nice find. So yeah, I guess there's no magic in this world — Dici, Jul 31 '20 at 20:52
@pjs yes. Just make some pen&paper tests with a "maximum" value of 15 that overflows to -16. This works since integral types in java form a [mathematical ring](https://en.wikipedia.org/wiki/Ring_(mathematics)). — Turing85, Jul 31 '20 at 20:52
@Turing85 I agree that mathematically it's a ring. I'm asking about whether the actual implementation conforms with the math abstraction. — pjs, Jul 31 '20 at 21:00
@pjs yes. [`Integer.MAX_VALUE + 1 == Integer.MIN_VALUE; Integer.MIN_VALUE - 1 == Integer.MAX_VALUE;`](https://ideone.com/y48sjb) — Turing85, Jul 31 '20 at 21:04
@Turing85 Meh, some test with some implementation is somewhat unsatisfying. Might want to link to [the specs](https://docs.oracle.com/javase/specs/jls/se14/html/jls-15.html#jls-15.18.2). — superb rain, Jul 31 '20 at 21:06
@superbrain well, I am not always in the mood to crawl the JLS ;) espeicially not if it's a section I am not familiar with. But yes. There you have it. — Turing85, Jul 31 '20 at 21:08
@Turing85 Me, neither. That's the only thing I know in the entire JLS. I despise Java :-) — superb rain, Jul 31 '20 at 21:09

WJS · Answer 1 · 2020-07-31T21:04:42.520

2

Two variables but you still have to swap.

public static int gcd(int r, int s) {
    while (s != 0) {
        r %= s;
        // swap them
        r ^= s;
        s ^= r;
        r ^= s;
    }
    return r;
}

Another possibility (but it wouldn't be Java) is to write a routine in byte code, store it in a byte[] array and execute it as a Java method. If using the internal stack is okay as it is in Python, then it should be okay here.

edited Jul 31 '20 at 21:04

answered Jul 31 '20 at 20:40

WJS

36,363
4
24
39

I think these answers are a little out of topic, it's more about swapping values than actually managing to write a GCD with only two variables (which has little interest in itself) – Dici Jul 31 '20 at 20:42
The author of the question stated "I want to keep the while loop and I don't want to use recursion." – Avi Jul 31 '20 at 20:43

comingstorm · Answer 2 · 2020-07-31T21:55:10.720

1

The reason for the difference is that Python has a tuple creation/decomposition feature, and Java does not.

As other answers have mentioned, you can do an integer swap with either xor or addition/subtraction. However, I suspect that for performance platforms like C or Rust, this is a false economy, and this hack will not speed things up or decrease resource usage. (If you're just in it for the challenge, though, it's legit, and probably the only solution)

Also, I don't think Java permits this trick for more general object references.

edited Jul 31 '20 at 21:55

answered Jul 31 '20 at 21:01

comingstorm

25,557
3
43
67

Doing a test run of 100M iterations of the same set of random numbers, the `single % op followed by three XOR's` is significantly faster than a `save, %, restore` version. The latter took about 25% more time. I reversed the order too. Not a `JMH` test but the deltas were significant. In both cases the GCD used the same while loop. Would like to see someone test this with the harness. – WJS Jul 31 '20 at 21:27
Hmm, I was thinking about performance platforms like C++, not Python where most of the load is in the interpreter. I will update and clarify my answer accordingly. – comingstorm Jul 31 '20 at 21:50
1

It is interesting to see that it helps in Java, thanks for checking! – comingstorm Jul 31 '20 at 21:56

score 1 · Answer 3 · answered Jul 31 '20 at 21:12

How about doing two steps in each loop iteration and not swapping at all?

private static int gcd(int p, int q) {
    // Return greatest common divisor using Euclid's Algorithm.
    while (q != 0) {
        p %= q;
        if (p == 0)
           return q;
        q %= p;
    }
    return p;
}

score 0 · Answer 4 · answered Jul 31 '20 at 20:38

0

Correct me If I'm wrong but, you can also do gcd operation using 2 variables in java.

private static int gcd(int p, int q) {
    // Return greatest common divisor using Euclid's Algorithm.
    int temp;
    while (p != q) {
        if(p > q)
            p = p - q;
        else
            q = q - p;
    }
    return q;
}

answered Jul 31 '20 at 20:38

Ahmet

7,527
3
23
47

This isn't directly equivalent because you can end up doing an absurd amount of subtractions (N) if one of the numbers is huge (N) and the other is small (e.g., 1). You need the modulo (`%`) to avoid this problem. – Avi Jul 31 '20 at 20:42

score 0 · Answer 5 · answered Jul 31 '20 at 20:43

0

Python might be adding some synthetic sugar on top of the "exclusive or" operator. This is a bitwise operation to swap values of two different variables without using a temporary variable.

See Java example below:

a = a^b;
b = a^b;
a = a^b;

See https://en.wikipedia.org/wiki/XOR_swap_algorithm

answered Jul 31 '20 at 20:43

Rod Caldas

56
4

Haha not bad. On the more general question of swapping, note this would only work for integers while Python's syntax applies to any type (in fact, it also works if `a` and `b` are of a different type) – Dici Jul 31 '20 at 20:47

Turing85 · Answer 6 · 2020-07-31T22:15:56.917

Aside from the given examples, there is a well known algorithm to swap two integer variables a and b without the use of a third variable:

// given: two int-variables a and b
a += b;
b = a - b;
a -= b
// result: a and b have been swapped

If we now first calculate a % b and assign it to a, all that is left to do is to swap a and b:

// given: two int-variables a and b
a = a % b;
a += b;
b = a - b;
a -= b
// result: the new value of a is b, while the new value of b is a % b

This even works if the addition a + b overflows, since it is reversed by the subtractions.

As an aside: I see this as a code golf. Unless one is under heavy memory constraint, I would not advice to use this solution.

How can I only use 2 variables in Java as with the Python code?

6 Answers6