考拉兹猜想数列 - 优化代码

Question

考拉兹猜想数列 - 优化代码

javaarraysoptimizationmathematical-optimizationcollatz

6

作为一个额外的任务，我们被要求找到产生最长collatz序列的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;
}

- spyr03

一种微小的优化是将 / 2 替换为 >>> 1。但这并不能带来太大的改善。 - Martijn Courteaux

我并不是一个大英雄，但维基百科上有一个很好的章节介绍了它。你可以进行一些预计算，使你能够一次进行 k 次迭代。https://en.wikipedia.org/wiki/Collatz_conjecture#Optimizations - Martijn Courteaux

我只是在学习不太常见的（也就是非算术）运算符，所以这很有趣，而且可能很有用，但维基百科的文章已经超出了我目前的编程范围。不过我一定会尝试去研究它的。 - spyr03

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- maaartinus · Accepted Answer

你可以这样做：

你可以做一些像这样的事情

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）和过滤掉一些不太有希望的值，可以在范围 1 .. 1e10 中确定最大值，耗时 57 秒。