Why does changing int to long speed up the execution? [duplicate]

Question

I was trying to solve problem #14 from Project Euler, and had written the following C#...

int maxColl = 0;
int maxLen = 0;
for (int i = 2; i < 1000000; i++) {
  int coll = i;
  int len = 1;
  while (coll != 1) {
    if (coll % 2 == 0) {
      coll = coll / 2;
    } else {
      coll = 3 * coll + 1;
    }
    len++;
  }
  if (len > maxLen) {
    maxLen = len;
    maxColl = i;
  }
}

Trouble was, it just ran and ran without seeming to stop.

After searching for other people's solution to the problem, I saw one looking very similar, except that he had used long instead of int. I didn't see why this should be necessary, as all of the numbers involved in this problem are well within the range of an int, but I tried it anyway.

Changing int to long made the code run in just over 2 seconds.

Anyone able to explain this to me?

Answer 1

When i equals 113383, the 3X+1 sequence at some point exceeds the maximum value of an int, so 3 * coll + 1 overflows and becomes negative:

113383 → 340150 → ... → 1654740898 → 827370449 → −1812855948 → −906427974 → ...

Eventually, the sequence winds up in the following cycle of negative numbers:

... → −17 → −50 → −25 → −74 → −37 → −110 → −55 → −164 → −82 → −41 → −122 → −61 → −182 → −91 → −272 → −136 → −68 → −34 → −17

This cycle doesn't include 1, so your loop never terminates.

Using long instead of int ensures that coll never overflows.

Answer 2

Your integers are overflowing and becoming negative.
Therefore, your loop never actually terminates.
If you wrap your code in a checked block, you'll see an overflow exception instead.

long is large enough to store the values you need, so that works fine.