More about abstraction quality

I would like to continue the discussion of abstraction quality by looking at just what it takes to add three integers correctly whenever it is possible to do so.

Let's keep it simple: We have three integers i, j, and k, and we wish to compute their sum, provided that it is possible to represent the sum as an integer. As with C and C++, we will assume that any sum, even an intermediate sum, that cannot fit in an integer causes undefined behavior.

If i, j, and k are all positive (or zero), there's no problem: We don't care if the final sum overflows, because if it does, we can't represent the result anyway. If the final sum doesn't overflow, the intermediate sum can't overflow either, so we don't need to worry about it. A similar argument applies if i, j, and k are all negative or zero.

The fun comes when the quantites to be summed have different signs, because if we add the two quantities that happen to have the same sign, that intermediate sum might overflow even when the final result doesn't.
Accordingly, we have to be sure that whenever two of the quantities have different signs, we add those two first, and only then add the third.

Our algorithm, then, looks like this: If i and j have different signs, the result is (i+j)+k. Because i+j cannot overflow (because i and j have different signs), the only possible overflow comes when the final result wouldn't have fit in an integer anyway.

If i and j have the same sign, then either k has the same sign as the other two or it has a different sign. If it has the same sign, it doesn't matter in what order we add the three quantities. If it has a different sign, then i+(j+k) will give the right answer whenever it is possible to do so, for the same reason that (i+j)+k worked before.

In other words, we can express the algorithm this way:

if (sign(i) == sign(j))
    sum = i + (j + k);
else
    sum = (i + j) + k;

This is the kind of code that deserves a substantial comment to explain what is going on.

This example should show you why high-quality abstractions are often hard to achieve: Even something as simple as the sum of three integers is surprisingly difficult to compute correctly. If you are still unconvinced of the difficulty of such problems, you might try computing the sum of an arbitrary number of integers.

Posted by Andrew Koenig at 05:34 PM  Permalink