为什么改变int以加快执行速度？

Question

我试图从Project Euler解决问题#14,并编写了以下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;
  }
}

麻烦的是,它只是跑来跑去,似乎没有停止.

在寻找其他人解决问题的方法之后,我看到一个看起来非常相似,只是他用了long而不是int.我不明白为什么这是必要的,因为这个问题所涉及的所有数字都在int的范围内,但无论如何我都试过了.

将int更改为long使代码在2秒内运行.

有人能向我解释一下吗？

Answer 1

当i等于113383时,某个点的3X + 1序列超过了a的最大值int,因此3 * coll + 1溢出并变为负数:

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

最终,序列在下面的负数循环中结束:

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

此循环不包括1,因此您的循环永远不会终止.

使用long而不是int确保coll永不溢出.

Answer 2

你的整数溢出并变得消极.
因此,您的循环永远不会终止.
如果将代码包装在一个checked块中,则会看到溢出异常.

long 足以存储您需要的值,因此工作正常.