{"id":35493,"date":"2005-05-31T09:03:22","date_gmt":"2005-05-31T09:03:22","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/2005\/05\/31\/using-modular-arithmetic-to-avoid-timing-overflow-problems\/"},"modified":"2005-05-31T09:03:22","modified_gmt":"2005-05-31T09:03:22","slug":"using-modular-arithmetic-to-avoid-timing-overflow-problems","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20050531-22\/?p=35493","title":{"rendered":"Using modular arithmetic to avoid timing overflow problems"},"content":{"rendered":"

In an earlier article<\/a>, I presented a simple way of avoiding timing overflows which seemed to create a bit of confusion.\n The short version: Given a starting time start<\/strong>, an ending time end<\/strong> and an interval interval<\/strong>, the way to check whether the interval has elapsed is to use the expression end - start >= interval<\/code>. The naive expression end >= start + interval<\/code> suffers from integer overflow problems.\n To simplify the discussion, let’s operate in base-100 instead of base-232<\/sup>. The same logic works, but I think operating in base-100 will be easier to follow.\n Base-100 means that we remember only the last two digits of any number. Consider a starting time of start = 90<\/code> and an interval of interval = 10<\/code>. Using the wrong expression yields end >= start + interval = 90+10 = 100 = 0<\/code>. In other words, end >= 0<\/code> which is always true since end<\/code> has the range 0...99<\/code>. As a result, the wrong expression will think that the interval has expired prematurely.\n Using the correct expression, we have end - 90 >= 10<\/code>. Of the numbers 0..99<\/code>, the ones that give a difference less than 10 are 90<\/code> through 99<\/code>. Once end = 0<\/code>, the result is 0 - 90 = 10<\/code>, which correctly indicates that 10 ticks have elapsed since 90 once the timer reaches 0.\n You can work through a similar mistake using start = 89<\/code> instead of start = 90<\/code>; in this case, the wrong expression becomes end >= start + interval = 89 + 10 = 99<\/code>, or in other words, end >= 99<\/code>. This has the opposite problem from the previous case, namely that the expression will fail to detect that the interval has expired once the timer rolls over.\n But why does the end - start<\/code> expression work? It’s very simple: You just have to remember your rules of arithmetic from elementary school.\n (x - c) - (y - c) = x - c - y + c = x - y <\/code>\n In other words, subtracting the same value from both terms of a difference does not affect the final value. This rule applies even to modular arithmetic (because, as the mathematicians like to say, the set of integers modulo n<\/i> form an additive group).\n This rule is useful because it lets you delay the overflow as long as possible by subtracting the starting point from all your time markers; it has no effect upon time intervals. Wouldn’t it be great if start = 0<\/code>? Then the overflow won’t happen for 100 ticks. Well, you can act “as if” the starting point were start = 0<\/code> by simply subtracting start<\/code> from all your time markers.\n Those who prefer a graphical view can think of time passing as the hands around a clock (which wraps around at 60 minutes, say). When you decide to record your start point, rotate the clock so that the “12” precisely lines up with wherever the hand happens to be. You can now read off the elapsed time directly from your rotated clock. Rotating your clock is the same as subtracting (or adding) a constant to all time markers.\n Of course, this trick falls apart once you have to measure time intervals that come close to the wraparound time of your timer. In our 100-tick timer, for example, trying to measure the passage of 90 ticks is very difficult because there is only a 10-tick window where the inequality is satisfied. If we fail to catch the timer during that window, we miss it and have to wait another 90 ticks.<\/p>\n

So don’t do that. In practical terms, this means that you shouldn’t use GetTickCount<\/code> to measure time intervals longer than 15 days. <\/p>\n","protected":false},"excerpt":{"rendered":"

In an earlier article, I presented a simple way of avoiding timing overflows which seemed to create a bit of confusion. The short version: Given a starting time start, an ending time end and an interval interval, the way to check whether the interval has elapsed is to use the expression end – start >= […]<\/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-35493","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"

In an earlier article, I presented a simple way of avoiding timing overflows which seemed to create a bit of confusion. The short version: Given a starting time start, an ending time end and an interval interval, the way to check whether the interval has elapsed is to use the expression end – start >= […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/35493","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=35493"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/35493\/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=35493"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=35493"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=35493"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}