{"id":92621,"date":"2015-12-14T07:00:00","date_gmt":"2015-12-14T22:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/?p=92621"},"modified":"2019-03-13T12:22:49","modified_gmt":"2019-03-13T19:22:49","slug":"20151214-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20151214-00\/?p=92621","title":{"rendered":"Calculating integer factorials in constant time, taking advantage of overflow behavior"},"content":{"rendered":"

For some reason, people on StackOverflow calculate factorials a lot. (Nevermind that it’s not necessarily the best way to evaluate a formula<\/a>.) And you will see factorial functions like this: <\/p>\n

\nint factorial(int n)\n{\n if (n < 0) return -1; \/\/ EDOM\n int result = 1;\n for (int i = 2; i <= n; i++) result *= i;\n return result;\n}\n<\/pre>\n
But you can do better than this by taking advantage of undefined behavior<\/a>. <\/p>\n
Since signed integer overflow results in undefined behavior in C\/C++, you can assume that the result of the factorial does not exceed INT_MAX<\/code>, which is 2147483647 for 32-bit signed integers. This means that n<\/var> cannot be greater than 12. <\/p>\n
So use a lookup table. <\/p>\n
\nint factorial(int n)\n{\n static const int results[] = {\n    1,\n    1,\n    1 * 2,\n    1 * 2 * 3,\n    1 * 2 * 3 * 4,\n    1 * 2 * 3 * 4 * 5,\n    1 * 2 * 3 * 4 * 5 * 6,\n    1 * 2 * 3 * 4 * 5 * 6 * 7,\n    1 * 2 * 3 * 4 * 5 * 6 * 7 * 8,\n    1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9,\n    1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10,\n    1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11,\n    1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12,\n };\n if (n < 0) return -1; \/\/ EDOM\n return results[n]; \/\/ undefined behavior if n > 12\n}\n<\/pre>\n
(If you have 64-bit signed integers, then the table needs to go up to 20.) <\/p>\n
The fact that you have undefined behavior if n<\/var> > 12 is hardly notable, because the original code also had undefined behavior if n<\/var> > 12. You just replaced one undefined behavior with another. <\/p>\n
If you want to simulate two’s complement overflow, for example, to preserve bug-for-bug compatibility, or because the function was defined to compute unsigned instead of signed factorial,¹ then you can do that by extending the table just a little bit more. You will need only entries up to 33! because because 34! is an exact multiple of 2³²<\/a>. The result of factorial(n)<\/code> is zero for n<\/var> ≥ 34, assuming 32-bit integers. <\/p>\n
\nint factorial(int n)\n{\n static const int results[] = {\n          1, \/\/ 0!\n          1, \/\/ 1!\n          2, \/\/ 2!\n          6, \/\/ 3!\n         24, \/\/ 4!\n        120, \/\/ 5!\n        720, \/\/ 6!\n       5040, \/\/ 7!\n      40320, \/\/ 8!\n     362880, \/\/ 9!\n    3628800, \/\/ 10!\n   39916800, \/\/ 11!\n  479001600, \/\/ 12!\n 1932053504, \/\/ 13!\n 1278945280, \/\/ 14!\n 2004310016, \/\/ 15!\n 2004189184, \/\/ 16!\n 4006445056, \/\/ 17!\n 3396534272, \/\/ 18!\n  109641728, \/\/ 19!\n 2192834560, \/\/ 20!\n 3099852800, \/\/ 21!\n 3772252160, \/\/ 22!\n  862453760, \/\/ 23!\n 3519021056, \/\/ 24!\n 2076180480, \/\/ 25!\n 2441084928, \/\/ 26!\n 1484783616, \/\/ 27!\n 2919235584, \/\/ 28!\n 3053453312, \/\/ 29!\n 1409286144, \/\/ 30!\n  738197504, \/\/ 31!\n 2147483648, \/\/ 32!\n 2147483648, \/\/ 33!\n };\n if (n < 0) return -1; \/\/ EDOM\n if (n > 33) return 0; \/\/ overflowed to zero\n return results[n];\n<\/pre>\n
I didn’t calculate all those numbers myself. I wrote a program to do it. <\/p>\n
\nclass Program\n{\n public static void Main() {\n  uint result = 1;\n  uint n = 0;\n  while (result != 0) {\n   System.Console.WriteLine(\" {0,10}, \/\/ {1}!\", result, n);\n   result *= ++n;\n  }\n }\n}\n<\/pre>\n
Extending the above algorithm to 64-bit integers is left as an exercise. <\/p>\n
¹ Unsigned arithmetic is defined by the C\/C++ standards to be modulo 2ⁿ<\/var> for some n<\/var>. <\/p>\n","protected":false},"excerpt":{"rendered":"
Too high! Too high!<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-92621","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
Too high! Too high!<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/92621","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=92621"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/92621\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=92621"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=92621"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=92621"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}