{"id":5511,"date":"2018-08-19T13:00:06","date_gmt":"2018-08-19T13:00:06","guid":{"rendered":"http:\/\/writeasync.net\/?p=5511"},"modified":"2018-08-15T15:48:09","modified_gmt":"2018-08-15T15:48:09","slug":"edge-cases-overflow","status":"publish","type":"post","link":"http:\/\/writeasync.net\/?p=5511","title":{"rendered":"Edge cases: overflow"},"content":{"rendered":"

Consider this (rather suboptimal) prime factorization<\/a> algorithm:<\/p>\n

\r\n    public static class MyMath\r\n    {\r\n        public static IEnumerable<KeyValuePair<int, int>> Factor(int n)\r\n        {\r\n            if (n < 2)\r\n            {\r\n                yield break;\r\n            }\r\n\r\n            \/\/ Handle factors of 2 first\r\n            int p = 0;\r\n            while ((n & 1) == 0)\r\n            {\r\n                n \/= 2;\r\n                ++p;\r\n            }\r\n\r\n            if (p != 0)\r\n            {\r\n                yield return new KeyValuePair<int, int>(2, p);\r\n            }\r\n\r\n            \/\/ Now check every odd number\r\n            for (int f = 3; f <= n; f += 2)\r\n            {\r\n                p = 0;\r\n                int r = 0;\r\n                while (r == 0)\r\n                {\r\n                    int m = Math.DivRem(n, f, out r);\r\n                    if (r == 0)\r\n                    {\r\n                        n = m;\r\n                        ++p;\r\n                    }\r\n                }\r\n\r\n                if (p != 0)\r\n                {\r\n                    yield return new KeyValuePair<int, int>(f, p);\r\n                }\r\n            }\r\n        }\r\n    }\r\n<\/pre>\n
You can run it like so and see that it returns the proper factorization for a variety of Int32<\/a> values:<\/p>\n
\r\n            Console.WriteLine(string.Join(';', MyMath.Factor(1)));\r\n            \/\/ Output: <empty string>\r\n\r\n            Console.WriteLine(string.Join(';', MyMath.Factor(1024)));\r\n            \/\/ Output: [2, 10]\r\n\r\n            Console.WriteLine(string.Join(';', MyMath.Factor(555555)));\r\n            \/\/ Output: [3, 1];[5, 1];[7, 1];[11, 1];[13, 1];[37, 1]\r\n\r\n            Console.WriteLine(string.Join(';', MyMath.Factor(2048002048)));\r\n            \/\/ Output: [2, 11];[101, 1];[9901, 1]\r\n<\/pre>\n
In fact, it works properly for any possible Int32 — except<\/em> one very critical value. Can you spot the defect<\/a>?<\/p>\n
.<\/p>\n
.<\/p>\n
.<\/p>\n
.<\/p>\n
.<\/p>\n
.<\/p>\n
The title of the post may have given it away, but the problem is in the for<\/code> loop boundary. If n == int.MaxValue<\/code>, the check f <= n<\/code> will always succeed. Because of integer overflow<\/a> and the lucky coincidence that 231<\/sup> - 1<\/a> (AKA int.MaxValue<\/code>) is prime, f<\/code> will be incremented beyond this value and wrap around to the negatives -- specifically, -231<\/sup> + 1 since we increment by 2. From there, the loop will keep running, continuing to wrap around forever and ever.<\/p>\n
I had originally written this code to benchmark some simple factoring algorithms. While I was prescient enough to write a unit test for this particular case, I was still initially confused and surprised by its exceedingly long (in fact, infinite) running time.<\/p>\n
There are several possible fixes for this problem. Perhaps the best one here is to optimize the algorithm and change the upper bound to the square root of the number. (For example, when using trial division<\/a> to factor the number 1,000,003, it is not necessary to check any factor larger than 1,000 since the product 1001 x 1001 will exceed the original number.) While that happens to work in this particular algorithm, there may not be an easy way to avoid the MaxValue comparison in other situations.<\/p>\n
Another quick fix which works in most general cases is to use long<\/code> (Int64<\/code>) for the loop counter f<\/code> instead of int<\/code>. This pushes the overflow boundary far higher, at the cost of a few well-placed cast operations. If you are running this code on an x64 processor, it is highly likely that the JIT compiler<\/a> is already using 64-bit registers<\/a> anyway so there should be no major performance impact.<\/p>\n
Moral of the story: boundary values<\/a> are still important; try passing int.MaxValue<\/code> in your unit tests.<\/p>\n","protected":false},"excerpt":{"rendered":"
Consider this (rather suboptimal) prime factorization algorithm: public static class MyMath { public static IEnumerable<KeyValuePair<int, int>> Factor(int n) { if (n < 2) { yield break; } \/\/ Handle factors of 2 first int p = 0; while ((n &… <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[51],"tags":[],"class_list":["post-5511","post","type-post","status-publish","format-standard","hentry","category-testing"],"_links":{"self":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5511","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=5511"}],"version-history":[{"count":2,"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5511\/revisions"}],"predecessor-version":[{"id":5513,"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5511\/revisions\/5513"}],"wp:attachment":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=5511"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=5511"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=5511"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}