Can you trust fixed-bit computer arithmetic?

Suppose that you have 10 pictures, and all lined up, they take 100 pixels. Is it safe to say that each picture has a width of x pixels if 10 x = 100?

We all know that a x = b has a unique solution x as long as a is non-zero. If you work with integers, then you can say that there is at most one solution.

Unfortunately, computer arithmetic is uglier. Over 32-bit integers, the equation a x= 0 has 231 solutions if a = 231. Indeed, as long as x is even, 231 x = 0.

But notice how I had to choose a large value of a to make computer arithmetic look bad. What if a is small? Certainly, if a = 1, then there is exactly one solution. If a = 2, then there are at most two solutions: 2 x can take any odd even and the most significant bit of x is discarded.

We can generalize this result a bit: if a = 2L, then there are at most 2L solutions x.

But we can generalize it even further! We have that a x = b has at most 2L integer solutions x if a is an L-bit non-zero integer. That is, as long as a is small, then a x = b has few solutions. The proof is technical, but not difficult:

Proof (Sketch). Let a is an L-bit non-zero integer and suppose we work with K-bit arithmetic. We consider the equation a x div 2L = b modulo 2K – L. Let j be the first non-zero bit of a. E.g., if a = 7 then j = 1. Because ai = 0 for i < j, we have that the value of a x 2L is independent of the last j -1 bits of x. Moreover, we have that the most significant bit of x which matters (xK-j+1) only matters for the last bit of a x. We can solve for this last effectual bit xK-j+1 in (ax)K = bK-L as a function of bK-L, a and the lesser bits of x. We can continue solving for the lesser bits of x by consider a x = b minus the last bit. (In effect, we have reduced the problem in an integer ring with K bits to a similar problem in integer ring with K-1 bits.) After K-L steps, the process terminates (K=L) leaving L bits in x that can be set freely generating 2L different solutions. QED

Getting back to our orignal problem: Because the integer 10 can be written using 4 bits (0b1010), the equation 10 x = 100 has at most 24 = 16 solutions. So if x was just picked at random, chances are good that the assertion would fail: for 32-bit integers, the probability of a false positive is at most 15/232 which is much, much less than 1%.

Further reading: M. Dietzfelbinger, Universal hashing and k-wise independent random variables via integer arithmetic without primes, in: STACS’96, 1996.

Published by

Daniel Lemire

A computer science professor at the University of Quebec (TELUQ).

3 thoughts on “Can you trust fixed-bit computer arithmetic?”

Leave a Reply

Your email address will not be published. The comment form expects plain text. If you need to format your text, you can use HTML elements such strong, blockquote, cite, code and em. For formatting code as HTML automatically, I recommend tohtml.com.

You may subscribe to this blog by email.