collatz序列优化代码

Question

作为作业的附加问题，我们被要求找到产生最长collatz序列的10个起始数(n)。(0

我注意到了一些小的优化，比如从最大到最小开始，这样添加到数组中的工作就更少了，只计算10,000,000/2^10 (=9765625)到10,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000，有人能帮忙吗？

相关编码序列搜索Alg

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-th减半发生时为止。基于此(使用k=17)和过滤掉一些没有希望的值。，我的最佳结果是57秒，用于确定范围内的最大1 .. 1e10。