CODEWITHSUNDEEP
javaalgorithmfunctionmathequation
Hither Joe
Hither Joe

Reputation: 115

Why is this Szudzik Elegant Pairing giving wrong result?

I'm pairing two numbers to form a unique number using elegant pairing. But when I pair two same numbers above 67108863 e.g "pair(67108864,67108864)" it gives me 4503599761588224. When I want to unpair it, it's going to give me (-1,67108865). I then tried to pair (-1,67108865), it gives me 4503599761588224 also. All other different numbers gives a unique number or same number under 67108864, I can pair and unpair them unless I pair the same number above 67108863; (67108864,67108864),(507108864,507108864), etc.

Is there an error in my code or I just found an issue with Szudzik Elegant Pairing Function?

/**
 *
 * @author HiltherJoe
 */
public class ElegantP {
    public static long pair(long x, long y) {
        return x >= y ? x * x + x + y : y * y + x;
    }
    public static long[] unpair(long z) {
        long b = (long) Math.sqrt(z);
        long a = z - b * b;
        return a < b ? new long[]{a, b} : new long[]{b, a - b};
    }
    public static void main(String[] args){
        int i = 67108864;
        long pairedNumber = pair(i, i);
        long[] unpair = unpair(pairedNumber);
        System.out.println("Paired Number is    " + pairedNumber);
        System.out.println("First unpaired Number is    " + unpair[0]+"    Second unpaired Number is    "+unpair[1]);
    }
}

Upvotes: 0

Views: 534

Answers (1)

user85421
user85421

Reputation: 29710

This code is using Math.sqrt() which does double calculation - the result is not exact enough. For 4503599761588224 (pair(67108864,67108864)), it is resulting in 67108865 instead of 67108864.

Use BigInteger.sqrt() (or any other exact method) and it should work:

long b = BigInteger.valueOf(z).sqrt().longValue();
long a = z - b * b;

for bigger number there is still the overflow risk as commented by SMA

Upvotes: 2

Related Questions