6

作为作业的附加问题，我们被要求找到产生最长 collat​​z 序列的 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
    }
}

存储算法

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;
}
4

1 回答 1

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 秒，用于确定 range 中的最大值1 .. 1e10。

于 2014-10-19T21:03:22.803 回答