java - 在Java中优化Collat​​z猜想

Question

我正在开发一个程序，该程序使用 Collat​​z 猜想(如果 n 为奇数，则为 3n+1；如果 n 为偶数，则为 n/2)确定一个数变为 1 所需的步数。该程序每完成一次计算，就会将正在计算的数字加一，并测试它可以在几秒钟内计算出多少个数字。这是我目前的工作程序:

public class Collatz {
    static long numSteps = 0;
    public static long calculate(long c){
        if(c == 1){
            return numSteps;
        }
        else if(c % 2 == 0){
            numSteps++;
            calculate(c / 2);
        }
        else if(c % 2 != 0){
            numSteps++;
            calculate(c * 3 + 1);
        }
        return numSteps;
    }
    public static void main(String args[]){
        int n = 1;
        long startTime = System.currentTimeMillis();
        while(System.currentTimeMillis() < startTime + 60000){

            calculate(n);
            n++;
            numSteps = 0;
        }
        System.out.println("The highest number was: " + n);
    }
}

它目前可以在一分钟内计算大约 1 亿个数字，但我正在寻找有关如何进一步优化程序以使其在一分钟内计算更多数字的建议。任何和所有建议将不胜感激:)。

Answer 1

你可以

• 通过假设 c % 2 == 0 为假而不是 c % 2 != 0 必须为真来优化计算方法。您还可以假设 c * 3 + 1 必须是偶数，这样您就可以计算 (c * 3 + 1)/2 并将 2 添加到 numSteps。您可以使用循环而不是递归，因为 Java 没有尾调用优化。

• 通过内存获得更大的进步。对于每个数字，您可以记住您得到的结果，如果在返回该值之前已经计算出该数字。你可能想对内存设置一个上限，例如不高于您要计算的最后一个数字。如果您不这样做，一些值将是最大值的许多倍。

为了你的利益

public class Collatz {
    static final int[] CALC_CACHE = new int[2_000_000_000];

    static int calculate(long n) {
        int numSteps = 0;
        long c = n;
        while (c != 1) {
            if (c < CALC_CACHE.length) {
                int steps = CALC_CACHE[(int) c];
                if (steps > 0) {
                    numSteps += steps;
                    break;
                }
            }
            if (c % 2 == 0) {
                numSteps++;
                c /= 2;
            } else {
                numSteps += 2;
                if (c > Long.MAX_VALUE / 3)
                    throw new IllegalStateException("c is too large " + c);
                c = (c * 3 + 1) / 2;
            }
        }
        if (n < CALC_CACHE.length) {
            CALC_CACHE[(int) n] = numSteps;
        }
        return numSteps;
    }

    public static void main(String args[]) {
        long n = 1, maxN = 0, maxSteps = 0;
        long startTime = System.currentTimeMillis();
        while (System.currentTimeMillis() < startTime + 60000) {
            for (int i = 0; i < 10; i++) {
                int steps = calculate(n);
                if (steps > maxSteps) {
                    maxSteps = steps;
                    maxN = n;
                }
                n++;
            }
            if (n % 10000000 == 1)
                System.out.printf("%,d%n", n);
        }
        System.out.printf("The highest number was: %,d, maxSteps: %,d for: %,d%n", n, maxSteps, maxN);
    }
}

打印

The highest number was: 1,672,915,631, maxSteps: 1,000 for: 1,412,987,847

更高级的答案是使用多线程。在这种情况下，使用带内存的递归更容易实现。

import java.util.stream.LongStream;

public class Collatz {
    static final short[] CALC_CACHE = new short[Integer.MAX_VALUE-8];

    public static int calculate(long c) {
        if (c == 1) {
            return 0;
        }
        int steps;
        if (c < CALC_CACHE.length) {
            steps = CALC_CACHE[(int) c];
            if (steps > 0)
                return steps;
        }
        if (c % 2 == 0) {
            steps = calculate(c / 2) + 1;
        } else {
            steps = calculate((c * 3 + 1) / 2) + 2;
        }
        if (c < CALC_CACHE.length) {
            if (steps > Short.MAX_VALUE)
                throw new AssertionError();
            CALC_CACHE[(int) c] = (short) steps;
        }
        return steps;
    }

    static int calculate2(long n) {
        int numSteps = 0;
        long c = n;
        while (c != 1) {
            if (c < CALC_CACHE.length) {
                int steps = CALC_CACHE[(int) c];
                if (steps > 0) {
                    numSteps += steps;
                    break;
                }
            }
            if (c % 2 == 0) {
                numSteps++;
                c /= 2;
            } else {
                numSteps += 2;
                if (c > Long.MAX_VALUE / 3)
                    throw new IllegalStateException("c is too large " + c);
                c = (c * 3 + 1) / 2;
            }
        }
        if (n < CALC_CACHE.length) {
            CALC_CACHE[(int) n] = (short) numSteps;
        }
        return numSteps;
    }

    public static void main(String args[]) {
        long maxN = 0, maxSteps = 0;
        long startTime = System.currentTimeMillis();
        long[] res = LongStream.range(1, 6_000_000_000L).parallel().collect(
                () -> new long[2],
                (long[] arr, long n) -> {
                    int steps = calculate(n);
                    if (steps > arr[0]) {
                        arr[0] = steps;
                        arr[1] = n;
                    }
                },
                (a, b) -> {
                    if (a[0] < b[0]) {
                        a[0] = b[0];
                        a[1] = b[1];
                    }
                });
        maxN = res[1];
        maxSteps = res[0];
        long time = System.currentTimeMillis() - startTime;
        System.out.printf("After %.3f seconds, maxSteps: %,d for: %,d%n", time / 1e3, maxSteps, maxN);
    }
}

打印

After 52.461 seconds, maxSteps: 1,131 for: 4,890,328,815

注意:如果我将第二个计算调用更改为

     steps = calculate((c * 3 + 1) ) + 1;

它打印

After 63.065 seconds, maxSteps: 1,131 for: 4,890,328,815