Rocky Rocky - 2 months ago 27
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;
}

Answer

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.
Comments