Improved version
#Improved version II upped the range to 100 million so that I could get meaningful numbers of milliseconds on my machine. This consistently gives under 1750 ms, compared to slightly over 2000 ms with the original. It also gives the lowest index for a given count, consistent with the results shown on the Collatz entry in Wikipedia.
#Improved version I upped the range to 100 million so that I could get meaningful numbers of milliseconds on my machine. This consistently gives under 1750 ms, compared to slightly over 2000 ms with the original. It also gives the lowest index for a given count, consistent with the results shown on the Collatz entry in Wikipedia.
Improved version
I upped the range to 100 million so that I could get meaningful numbers of milliseconds on my machine. This consistently gives under 1750 ms, compared to slightly over 2000 ms with the original. It also gives the lowest index for a given count, consistent with the results shown on the Collatz entry in Wikipedia.
In case you wonder what happened to the continue mentioned in my first paragraph, it has to move to after the maxLength check, and it seems to optimise better when incorporated into the existing for loop condition, perhaps due to branch prediction.
In case you wonder what happened to the continue mentioned in my first paragraph, it has to move to after the maxLength check, and it seems to optimise better when incorporated into the existing for loop condition, perhaps due to branch prediction.
The lower loop (which fills all power-of-two multiples of the outer index) is doing unnecessary work when i is even. If we find that vals[i] was already filled in by a previous iteration, then so was vals[2*i] and so on.
I improved run-time by about 5% simply by adding at the start of the outer loop:
if (vals[i]) {
continue;
}
It's usual to report the lowest starting value of those that give rise to the same length chain. The current code doesn't do that, because of the second loop. To give the same results as seen on OEIS, then we need to change the logic to update maxIndex and maxLength only after computing Collatz(i), and before the *=2 loop.
Finally, we don't want to be measuring printing time as well as computation, so move the setting of elapsed before the printing of max number.
#Improved version I upped the range to 100 million so that I could get meaningful numbers of milliseconds on my machine. This consistently gives under 1750 ms, compared to slightly over 2000 ms with the original. It also gives the lowest index for a given count, consistent with the results shown on the Collatz entry in Wikipedia.
I've also applied changes suggested in other reviews
#include <chrono>
#include <iostream>
const unsigned int N = 100'000'000;
unsigned short vals[N] = {};
int main() {
using namespace std::chrono;
// Time the program:
auto const startTime = steady_clock::now();
unsigned int maxIndex = 0;
unsigned int maxLength = 0;
// calculate Collatz length for each index, and memoize
for (unsigned int i = 2; i < N; ++i) {
unsigned long iCpy = i;
unsigned int ct = 0;
while (iCpy > 1) {
if (iCpy < N && vals[iCpy]) {
ct += vals[iCpy];
break;
}
iCpy = iCpy % 2
? 3 * iCpy + 1
: iCpy / 2;
++ct;
}
if (ct > maxLength) {
maxLength = ct;
maxIndex = i;
}
// Pre-fill power-of-two multiples of this result
for (iCpy = i; iCpy < N && !vals[i]; iCpy *= 2) {
vals[iCpy] = ct++;
}
}
auto elapsed = duration_cast<milliseconds>(steady_clock::now() - startTime);
// output the max index and length:
std::cout << "Max number: " << maxIndex << ", with length " << maxLength << '\n';
std::cout << "Program execution took " << elapsed.count() << "ms\n";
return 0;
}