# Speeding up a recursive Cantor pairing function

The Cantor Pairing function is a mathematical function which takes two integers and combines them into a single integer that is unique to that pair. This single integer can later be "unpaired" back into the two original, separate integers. Further information on this function can be found here and here.

The Cantor pairing function can be used to pair more than just two integers together, however this must be done in a smart manner, as the size of the output of this function can jump to astronomical levels very, very quickly, which explains why I'm using Java's BigInteger class in my code.

I've written a small utility-type class in Java which contains one method capable of recursively pairing two or more integers, and another method that can unpair a single integer back into n original integers (along with two private helper methods):

package pairing;

import java.math.BigInteger;
import java.util.Arrays;

public class CantorPair {

private CantorPair() {
}

// This method recursively pairs two or more integers into a single, unique integer
public static BigInteger pair(final BigInteger... integers) {

final int n = integers.length;

if (n == 0)
throw new IllegalArgumentException("Argument list length cannot be zero!");

final BigInteger x = integers;

if (n == 1)
return x;

final BigInteger y = integers;

// If we've only been given two integers, we can pair them together and return the result!
if (n == 2) {
}

// I've found that using a parallel stream here reduces the computation time significantly when pairing a large number of integers
return pair(Arrays.stream(makePairs(integers)).map(CantorPair::pair).parallel().toArray(BigInteger[]::new));
}

// This method recursively unpairs an integer into [n] separate integers
public static BigInteger[] unpair(final BigInteger integer, final int n) {
if (n < 1)
throw new IllegalArgumentException("Argument list length cannot be less than one!");
if (n == 1)
return new BigInteger[]{integer};
if (n == 2) {
.subtract(BigInteger.ONE)
.divide(BigInteger.TWO);
return new BigInteger[]{
};
}

final BigInteger[] result = new BigInteger[n];
final BigInteger[] splitIntegers = unpair(integer, 2);

final int nearestPowerOfTwo = nearestPowerOfTwo(n);

if (n == nearestPowerOfTwo) {
System.arraycopy(unpair(splitIntegers, n / 2), 0, result, 0, n / 2);
System.arraycopy(unpair(splitIntegers, n / 2), 0, result, n / 2, n / 2);
} else {
System.arraycopy(unpair(splitIntegers, n - (n - nearestPowerOfTwo)), 0, result, 0, (n - (n - nearestPowerOfTwo)));
System.arraycopy(unpair(splitIntegers, n - nearestPowerOfTwo), 0, result, (n - (n - nearestPowerOfTwo)), n - nearestPowerOfTwo);
}

return result;
}

// This method splits an array of integers into groups of two
private static BigInteger[][] makePairs(final BigInteger[] inputList) {
final BigInteger[][] result = new BigInteger[(int) Math.ceil(inputList.length / 2.0)][];
for (int i = 0; i < inputList.length; i += 2)
result[i / 2] = (i == inputList.length - 1) ? new BigInteger[]{inputList[i]} : new BigInteger[]{inputList[i], inputList[i + 1]};
return result;
}

// This method returns the nearest power of two that is less than or equal to [x]
private static int nearestPowerOfTwo(int x) {
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
return x ^ (x >> 1);
}


I am quite happy with the pair method, as I have used it to pair lists of 100000+ integers nearly instantly on my machine, however the unpair method does not preform nearly as well, especially once it is tasked with unpairing large integers. The computation time for this second method is long enough that I've used a stopwatch to time it - Integer lists which take the pair method ~1 second to complete take the unpair method more than 15 seconds to unpair. I've written a small test Class below which illustrates this fact (the variable numberOfIntegersToPair can be adjusted to change how many integers are paired/unpaired):

package main;

import java.math.BigInteger;
import java.util.stream.IntStream;

import pairing.CantorPair;

public class Main {
public static void main(String[] args) {

// Around 100000 is where I really begin to notice a slowdown on my machine
// Pairing completes instantly, but unpairing takes about 16 seconds
// The time difference between the two continues to noticeably increase after this
int numberOfIntegersToPair = 100000;

// Make an array containing [numberOfIntegersToPair] integers
BigInteger[] bigIntegers = IntStream.range(0, numberOfIntegersToPair)
.mapToObj(BigInteger::valueOf)
.toArray(BigInteger[]::new);

System.out.println("Starting to pair...");
// Let's pair our integer list and store the result
BigInteger pairedIntegers = CantorPair.pair(bigIntegers);
System.out.println("Done pairing!");

System.out.println("Starting to unpair...");
// Now let's unpair our large integer back into the smaller integers that formed it
// As the [numberOfIntegersToPair] increases, this function will begin to take significantly longer to complete
BigInteger[] unpairedIntegers = CantorPair.unpair(pairedIntegers, bigIntegers.length);
System.out.println("Done unpairing!");
}
}


I've tried to optimize this code as much as I know how (parallel streams, System.arraycopy instead of manual array copys, the use of arrays over lists wherever possible, etc.), and my adjustments have helped a bit (they helped speed up the pair function a lot), but I am unable to speed up the unpair method any further on my own. Perhaps there is nothing that can be done, but I'm open to any and all suggestions.

• I have seen in your pdf link an alternative method called elegantpair, it has the same performance of your method ? May 14, 2020 at 14:59
• @dariosicily Very similar performance, yes, I actually just tried it out (it sped up the unpair function by about 1-2 seconds). Although the "elegantpair" function requires fewer calculations to pair/unpair, it produces numbers which are larger than the Cantor function that I used above, which ultimately causes the calculations to take about the same time. May 14, 2020 at 16:43
• Ok, the only thing I'm seeing at the moment is it is possible to create variables inside the method to store repeatition of operations I'm seeing in the copy of array and maybe some other minor changes, but I doubt you can see a great improvement after modifies. Anyway I will submit an answer with my modifies , but I doubt it will help you with performance. May 14, 2020 at 17:09

Some minor changes can be applied to your unpair function, you have the following code in the body of 'unpair':

final BigInteger i = integer.multiply(BigInteger.valueOf(8)).add(BigInteger.ONE).sqrt()
.subtract(BigInteger.ONE)
.divide(BigInteger.TWO);
return new BigInteger[]{
};


You can store BigInteger.valueOf(8) and BigInteger.valueOf(3) into two constants to reuse in your calls:

private static final BigInteger EIGHT = BigInteger.valueOf(8);
private static final BigInteger THREE = BigInteger.valueOf(3);


Similar approach for this code present in your function:

if (n == nearestPowerOfTwo) {
System.arraycopy(unpair(splitIntegers, n / 2), 0, result, 0, n / 2);
System.arraycopy(unpair(splitIntegers, n / 2), 0, result, n / 2, n / 2);
} else {
System.arraycopy(unpair(splitIntegers, n - (n - nearestPowerOfTwo)), 0, result, 0, (n - (n - nearestPowerOfTwo)));
System.arraycopy(unpair(splitIntegers, n - nearestPowerOfTwo), 0, result, (n - (n - nearestPowerOfTwo)), n - nearestPowerOfTwo);
}


You can create variables storing repeated operations:

if (n == nearestPowerOfTwo) {
final int halfN = n / 2;
System.arraycopy(unpair(splitIntegers, halfN), 0, result, 0, halfN);
System.arraycopy(unpair(splitIntegers, halfN), 0, result, halfN, halfN);
} else {
System.arraycopy(unpair(splitIntegers, nearestPowerOfTwo), 0, result, 0, nearestPowerOfTwo);
final int nMinusNearestPowerOfTwo = n - nearestPowerOfTwo;
System.arraycopy(unpair(splitIntegers, nMinusNearestPowerOfTwo), 0, result, nearestPowerOfTwo, nMinusNearestPowerOfTwo);
}


Probably there is a slight improvement of performance due to the changes, but the core math still remains the same. Below the code of the unpair function modified:

private static final BigInteger EIGHT = BigInteger.valueOf(8);
private static final BigInteger THREE = BigInteger.valueOf(3);

// This method recursively unpairs an integer into [n] separate integers
public static BigInteger[] unpair(final BigInteger integer, final int n) {
if (n < 1)
throw new IllegalArgumentException("Argument list length cannot be less than one!");
if (n == 1)
return new BigInteger[]{integer};
if (n == 2) {
.subtract(BigInteger.ONE)
.divide(BigInteger.TWO);
return new BigInteger[]{
};
}

final BigInteger[] result = new BigInteger[n];
final BigInteger[] splitIntegers = unpair(integer, 2);

final int nearestPowerOfTwo = nearestPowerOfTwo(n);

if (n == nearestPowerOfTwo) {
final int halfN = n / 2;
System.arraycopy(unpair(splitIntegers, halfN), 0, result, 0, halfN);
System.arraycopy(unpair(splitIntegers, halfN), 0, result, halfN, halfN);
} else {
System.arraycopy(unpair(splitIntegers, nearestPowerOfTwo), 0, result, 0, nearestPowerOfTwo);
final int nMinusNearestPowerOfTwo = n - nearestPowerOfTwo;
System.arraycopy(unpair(splitIntegers, nMinusNearestPowerOfTwo), 0, result, nearestPowerOfTwo, nMinusNearestPowerOfTwo);
}

return result;
}

• I know there wasn't much to work with here so I appreciate you taking the time to look through it and sharing these suggestions. May 14, 2020 at 19:45
• @HomeworkHopper You are welcome. May 14, 2020 at 20:15