, 3 min read

# 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 2^{31} solutions if *a* = 2^{31}. Indeed, as long as *x* is even, 2^{31} *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* = 2^{L}, then there are at most 2^{L} solutions *x*.

But we can generalize it even further! We have that *a x* = *b* has at most 2^{L} integer solutions *x* if *a* is an *L*-bit non-zero integer. That is, **as long as** * a*__ is small, then__

*__ =__*

**a x***__ has few solutions__. The proof is technical, but not difficult:*

**b**Proof (Sketch). Let

ais anL-bit non-zero integer and suppose we work withK-bit arithmetic. We consider the equationa xdiv 2^{L}=bmodulo 2^{K – L}. Letjbe the first non-zero bit of a. E.g., ifa= 7 thenj= 1. Becausea= 0 for_{i}i < j, we have that the value ofa x2^{L}is independent of the lastj-1 bits ofx. Moreover, we have that the most significant bit ofxwhich matters (x) only matters for the last bit of_{K-j+1}a x. We can solve for this last effectual bitxin_{K-j+1}(ax)=_{K}bas a function of_{K-L}b,_{K-L}aand the lesser bits ofx. We can continue solving for the lesser bits ofxby considera x=bminus the last bit. (In effect, we have reduced the problem in an integer ring withKbits to a similar problem in integer ring withK-1 bits.) AfterK-Lsteps, the process terminates (K=L) leavingLbits inxthat can be set freely generating 2^{L}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 2^{4} = 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/2^{32} 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.