Почему изменение int позволяет ускорить выполнение?
Я пытался решить проблему проблемы 14 из Project Euler и написал следующий С#...
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 секунд.
Кто-нибудь может объяснить это мне?
Ответы
Ответ 1
Когда i равно 113383, последовательность 3X + 1 в некоторой точке превышает максимальное значение 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 никогда не будет переполняться.
Ответ 2
Ваши целые числа переполняются и становятся отрицательными.
Поэтому ваш цикл никогда не заканчивается.
Если вы поместите код в блок checked, вместо него вы увидите исключение переполнения.
long достаточно велик, чтобы хранить нужные вам значения, так что это нормально.
