Rocky - 2 months ago 27

C++ Question

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:

- I'm fairly sure that you are overflowing the
`int`

data type. Use a`uint64_t`

to make this far less likely. - You should only update
`superI`

and`superN`

outside of the while loop. This shouldn't matter, but it hurts performance. - 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. - 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.
```

Source (Stackoverflow)

Comments