collat​​z序列 - 优化代码

Question

作为一项任务的另一个问题,我们被要求找到产生最长的连环标记序列的10个起始数字(n).(其中0 <n <10,000,000,000)我编写的代码有望实现这一点,但我估计需要整整11个小时来计算答案.

我注意到了一些小的优化,比如从最大到最小,因此添加到阵列的次数减少了,只计算在10,000,000,000/2 ^ 10(= 9765625)和10,000,000,000之间,因为必须有10个长度较长的序列,但是我看不到任何我能做的事情.有人可以帮忙吗？

相关代码序列搜索算法

long[][] longest = new long[2][10]; //terms/starting number
long max = 10000000000l; //10 billion

for(long i = max; i >= 9765625; i--) {
    long n = i;
    long count = 1; //terms in the sequence

    while(n > 1) {
        if((n & 1) == 0) n /= 2; //checks if the last bit is a 0
        else {
            n = (3*n + 1)/2;
            count++;
        }
        count++;
    }
    if(count > longest[0][9]) {
        longest = addToArray(count, i, longest);
        currentBest(longest); //prints the currently stored top 10
    }
}

存储alg

public static long[][] addToArray(long count, long i, long[][] longest) {
    int pos = 0;
    while(count < longest[0][pos]) {
        pos++;
    }
    long TEMP = count; //terms
    long TEMPb = i; //starting number
    for(int a = pos; a < longest[0].length; a++) {
        long TEMP2 = longest[0][a];
        longest[0][a] = TEMP;
        TEMP = TEMP2;

        long TEMP2b = longest[1][a];
        longest[1][a] = TEMPb;
        TEMPb = TEMP2b;
    }
    return longest;
}

Answer 1

你可以做类似的事情

while (true) {
    int ntz = Long.numberOfTrailingZeros(n);
    count += ntz;
    n >>>= ntz; // Using unsigned shift allows to work with bigger numbers.
    if (n==1) break;
    n = 3*n + 1;
    count++;
}

它应该更快，因为它一次执行多个步骤并避免不可预测的分支。numberOfTrailingZeros是 JVM 固有的，在现代桌面 CPU 上只需要一个周期。然而，它的效率不是很高，因为零的平均数量只有 2 个。

维基百科解释了如何同时执行多个步骤。这是基于这样的观察：知道k最低有效位足以确定直到k第-次减半发生时的未来步骤。基于此（使用k=17）并过滤掉一些无希望的值，我的最佳结果是 57 秒来确定范围 中的最大值1 .. 1e10。