|Date:||September 17, 2003 / year-entry #67|
|Summary:||Exercise: Why do we use the formula c = a + (b-a)/2 instead of the simpler c = (a+b)/2? Answer: To avoid integer overflow in the computation of a+b. Here, a and b are window coordinates, and the window can be anywhere. If the window were placed at extreme coordinates like (MAXLONG,MAXLONG), then the arithmetic...|
Exercise: Why do we use the formula
Answer: To avoid integer overflow in the computation of
Note that the alternate formula
Integer overflow was one of the Windows 95 application compatibility bugs that I had to deal with. There was a DOS game that wanted to do a binary search, and instead of using indices, they attempted to average the two pointers together:
BYTE *low = ...; BYTE *high = ...; BYTE *mid = ((UINT)low + (UINT)high)/2;
This worked as long as the game was being run under an operating system without virtual
memory, because the "low" and "high" pointers would both be comparatively small numbers
(nobody had machines with 2GB of RAM), so the sum
Windows 95 ran these DOS games, but under a DPMI server that supported virtual memory. The DPMI specification permits the server to put memory anywhere, and we put our memory at the high end of the address space.
This program then overflowed in its attempt to average the two pointers and crashed.
So be careful how you average two values together. It's harder than you think.
<-- Back to Old New Thing Archive Index