Rocky - 1 year ago 193
C++ Question

C++ Collatz Conjecture Optimization

In ProjectEuler problem #14, one needs to find the longest Collatz chain, up to 1 million. I found a halfway decent way to do so, however, it feels like I'm just being stupid because I can't find a way to make this code more efficient (the code is supposed to only print out the solution, after it tests 1 to 1 million, but hasn't printed anyting out after 10 minutes). Am I tackling this problem the wrong way, or is there a way to optimize my existing code?

``````#include <iostream>
using namespace std;

int main()
{
int i;
int x;
int n;
int superN;
int superI;

superN = 0;
superI = 0;

for (i = 1; i <= 1000000; i++) {
x = i;
n = 1;

do {
if (x % 2 == 0) {
x = x / 2;
}

if (x % 2 == 1 && x != 1) {
x = 3 * x + 1;
}

n++;

if (n > superN) {
superN = n;
superI = i;
}
} while (x != 1);
}

cout << "The number " << superI << " ran for " << superN << " terms.";
system("pause");
return 0;
}
``````

You've got a few small problems:

1. I'm fairly sure that you are overflowing the `int` data type. Use a `uint64_t` to make this far less likely.
2. You should only update `superI` and `superN` outside of the while loop. This shouldn't matter, but it hurts performance.
3. On each iteration you should only modify `x` once. You currently might modify it twice, which might cause you to fall into an infinite loop. And your calculation of `n` will be off as well.
4. Use memoization to improve performance by caching old results.

Applying this, you could come up with some code like this:

``````#include <cstdint>
#include <iostream>
#include <map>
using namespace std;

int main()
{
uint64_t i;
uint64_t x;
uint64_t n;
uint64_t superN;
uint64_t superI;

std::map<uint64_t, uint64_t> memory;

superN = 0;
superI = 0;

for (i = 1; i <= 1000000; i++) {
x = i;
n = 1;

do {
if (memory.find(x) != memory.end()) {
n += memory[x];
break;
}

if (x % 2 == 0) {
x = x / 2;
} else {
x = 3 * x + 1;
}

n++;
} while (x != 1);

if (n > superN) {
superN = n;
superI = i;
}

memory[i] = n;
}

cout << "The number " << superI << " ran for " << superN << " terms.\n";
system("pause");
return 0;
}
``````

Which takes 4 seconds to output:

``````The number 837799 ran for 556 terms.
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download