Ищите быстрый метод для преобразования логического [] в коде Грея в BigInteger и наоборот в Java

Question

Для ГА необходимы два метода:

BigInteger greyToBigInteger(boolean[]){...}

а также

boolean[] bigIntegerToGrey(BigInteger){...}

Например:

15 ---> {true,false,false,false}
and
{true,false,false,false} --> 15

Я не знаю, как сделать это очень быстро. Максимальное число для преобразования составляет 10^1125, поэтому для одного числа оно работает более 5 минут, если я это сделаю, как в примере из Википедии.

Answer 1

Я написал этот фрагмент кода, и он работает довольно быстро без каких-либо специальных уловок - на моем ноутбуке требуется менее 2 миллисекунд для преобразования заданного числа, которое меньше или равно 10^1125, в серый и обратно:

import java.math.BigInteger;
import java.util.Random;

public class GrayCode {

    public static void main(String[] args) {

        // actually 10^1125 is a number with max length of 3738 bits
        int bitLength = new BigInteger("10").pow(1125).bitLength();
        System.out.println("10^1125 is a number with max bit length = " + bitLength);
        new GrayCode().test(bitLength);
    }

    private void test(int bitLength) {
        long totalTime = 0;
        long numberOfTests = 1000;

        for (int n = 0; n < numberOfTests; n++) {
            // We don't include time needed for generation of a number
            BigInteger binary = generateBigInteger(bitLength);

            // here we start measuring execution time of single conversion
            long start = System.currentTimeMillis();

            // The conversion to gray and back
            boolean[] gray = bigIntegerToGrey(binary);  
            BigInteger back = grayToBigInteger(gray);

            // we sum up the conversion times to totalTime per this test suite
            totalTime += System.currentTimeMillis() - start;
        }
        System.out.println("We have run a "+numberOfTests+" tests, for a random numbers of "+bitLength+" bit length to convert to gray code and back to binary");
        System.out.println("The total execution time of this test was "+totalTime+" milliseconds, giving average convesion time of " + totalTime/1000d + " ms per single test ");

    }

    private BigInteger grayToBigInteger(boolean[] booleanGray) {
        BigInteger input = booleanToBigInteger(booleanGray);
        return grayToBinary(input);
    }

    private boolean[] bigIntegerToGrey(BigInteger binary) {
        BigInteger gray = binaryToGray(binary);
        return bigIntegerToBooleanArray(gray);
    }

    public boolean[] bigIntegerToBooleanArray(BigInteger number) {
        char[] binary = number.toString(2).toCharArray();
        boolean[] binaryBoolean = new boolean[binary.length];
        for (int n = 0; n < binary.length; n++) {
            if (binary[n] == '1') {
                binaryBoolean[n] = true;
            }
        }
        return binaryBoolean;
    }

    private BigInteger generateBigInteger(int numBits) {
        Random rnd = new Random();
        BigInteger number = new BigInteger(numBits, rnd);
        return number;
    }

    public BigInteger booleanToBigInteger(boolean[] binary) {
        StringBuilder sb = new StringBuilder();
        for (boolean b : binary) {
            sb.append(b ? '1' : '0');
        }
        return new BigInteger(sb.toString(), 2);
    }

    public BigInteger binaryToGray(BigInteger num) {
        return num.xor(num.shiftRight(1));
    }

    public BigInteger grayToBinary(BigInteger num) {
        BigInteger mask;
        for (mask = num.shiftRight(1); mask.compareTo(BigInteger.ZERO) != 0; mask = mask.shiftRight(1)) {
            num = num.xor(mask);
        }
        return num;
    }

}

результаты, достижения:

10^1125 is a number with max bit length = 3738
We have run a 1000 tests, for a number of 3738 bit length to convert to gray code and back to binary
The total execution time of this test was 1828 milliseconds, giving average convesion time of 1.828 ms per single test