checked でオーバーフローをチェックする

C#

Problem 14 のコラッツの問題で計算がいっこうに終わらないと思ったら、int で計算していたところがオーバーフローして、無限ループになっていたのが原因だったようだ。

C# では checked でオーバーフローがチェックできる仕組みがあるようなので、試してみました。

using System;

class Overflow {
    static int Collatz(int n) {
        int x = n;
        int step = 1;
        while (x != 1) {
            if (x % 2 == 0) {
                x = x / 2;
            }
            else {
                x = checked(3 * x + 1); // checked でオーバーフローをチェックします
            }
            step++;
        }
        return step;
    }

    public static void Main() {
        int n = 1;
        try {
            while (true) {
                Collatz(n);
                n++;
            }
        }
        catch (OverflowException) {
            Console.WriteLine("catched {0}", n);
        }
    }
}

checked で囲まれた式がオーバーフローすると、OverflowException 例外が発生します。

実行結果です。

% dmcs overflow.cs -out:a.exe
% mono a.exe
catched 113383

参考:

ちなみに、113383 から始まるコラッツの数列は以下のようになります。

113383 340150 170075 510226 255113 765340 382670 191335 574006 287003 861010 430505
1291516 645758 322879 968638 484319 1452958 726479 2179438 1089719 3269158 1634579
4903738 2451869 7355608 3677804 1838902 919451 2758354 1379177 4137532 2068766
1034383 3103150 1551575 4654726 2327363 6982090 3491045 10473136 5236568 2618284
1309142 654571 1963714 981857 2945572 1472786 736393 2209180 1104590 552295 1656886
828443 2485330 1242665 3727996 1863998 931999 2795998 1397999 4193998 2096999 6290998
3145499 9436498 4718249 14154748 7077374 3538687 10616062 5308031 15924094 7962047
23886142 11943071 35829214 17914607 53743822 26871911 80615734 40307867 120923602
60461801 181385404 90692702 45346351 136039054 68019527 204058582 102029291
306087874 153043937 459131812 229565906 114782953 344348860 172174430 86087215
258261646 129130823 387392470 193696235 581088706 290544353 871633060 435816530
217908265 653724796 326862398 163431199 490293598 245146799 735440398 367720199
1103160598 551580299 1654740898 827370449 2482111348 1241055674 620527837 1861583512
930791756 465395878 232697939 698093818 349046909 1047140728 523570364 261785182
130892591 392677774 196338887 589016662 294508331 883524994 441762497 1325287492
662643746 331321873 993965620 496982810 248491405 745474216 372737108 186368554
93184277 279552832 139776416 69888208 34944104 17472052 8736026 4368013 13104040
6552020 3276010 1638005 4914016 2457008 1228504 614252 307126 153563 460690 230345
691036 345518 172759 518278 259139 777418 388709 1166128 583064 291532 145766 72883
218650 109325 327976 163988 81994 40997 122992 61496 30748 15374 7687 23062 11531
34594 17297 51892 25946 12973 38920 19460 9730 4865 14596 7298 3649 10948 5474
2737 8212 4106 2053 6160 3080 1540 770 385 1156 578 289 868 434 217 652 326
163 490 245 736 368 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1