Subtraction is not comparison

http://www.tedunangst.com/flak/post/subtraction-is-not-comparison

by pdw • 12 years ago

90 64 12 years ago

seivadmas2• 12 years ago

WTF? The article states:

  x = 1987654321 and y = -1987654321? Then the difference between them is -319658654 (negative) which proves that x is less than y. That’s less than correct.

Which is completely 100% wrong. Surely the difference would be x - y i.e (1987654321 - (-1987654321)) = (1987654321 + 1987654321) = 3975308642.

Which is perfectly ok, because that's positive and so proves x is greater than y. So this comparison works just fine for negative integers...

Scaevolus• 12 years ago

(int32_t)3975308642 == -319658654

Overflow makes intuitive arithmetic do unusual things.

Similarly, using a+b/2 for binary search midpoints is wrong. http://googleresearch.blogspot.com/2006/06/extra-extra-read-...

imron2• 12 years ago

The writer assumes that the reader understands and knows about how integer overflows work in C.

bluedino• 12 years ago

Exactly, don't use subtraction for comparison in C.

The previous commenter may have entered that into say, a Python console where it wouldn't exhibit that behavior.

_almosnow• 12 years ago

Yeah but that's what happens when people become so adapted to their tools that they forget how real math/world works... and they even have the nerve to stand up for their flawed tools.

I actually like and use C everyday, but it would be aberrant for me to say essentially what the article implies: "A math algorithm is wrong because it doesn't work in C"

ufo• 12 years ago

Subtraction is comparison at the assembly level though. C sadly doesn't give any way to interact with the overflow flags though...

vardump3• 12 years ago

Yup. On pretty much any architecture I can think of, a CMP is exactly like a SUB that does not store result, but sets only flags.

haberman• 12 years ago

When something is easy at the hardware level but there is no easy way to express it in programs, it suggests a failure of the abstraction. Or more positively, room for improvement. I'd love to see some way that this can be expressed elegantly in C.

psyklic• 12 years ago

The way that C expresses it elegantly is via the comparison operator. The author is concerned that people try to be clever and use subtraction instead. Here is how the author corrected this error by using comparison operators instead of subtracting (in the tree man page):

    int
    intcmp(struct node *e1, struct node *e2)
    {
  -	  return (e1->i - e2->i);
  +	  return (e1->i < e2->i ? -1 : e1->i > e2->i);
    }

The ternary operator is necessary, because in C a relational operator is evaluated to 0 (false) or 1 (true). So, the author added a special case for returning a negative value (indicating the first argument should be sorted before the second).

fubarred2• 12 years ago

Having designed microcoded pipelined processors from gates on up in uni, that's true.

integer cmp x, y often reduces to microcode that effectively runs:

  - 3A: sub x, y, dummy_result (att syntax) <-- most likely^
  - 2A: sub copy_of_x, y (intel syntax)
  - 1A: push x, push y (or y, x), sub, update flags, pop

^ Depends heavily on the microarchitecture, because there's likely all sorts of extra features and ops that can be set in the same microinstruction cycle to implement the macroinstructions.

In signed 2's-complement (mostly everything), zero flag just checks that all result bits to be zero and the less than flag is just the result's MSB (negative result if 1).

Signed and unsigned have their under/overflow issues. Being able to detect that and handle it in code, rather than crashing or silently producing undefined results, can be important, such as safely re-callocing memory (multiply overflow). (There are other issues like pointer/slice index over/underflow too, and these are related problems.)

The issues are usually around whether branch-free code is absolutely necessary or whether predicting branches wrong would incur disastrous pipeline stall/s (greatly depends on the specific use-case, especially inner loops... don't prematurely overoptimize).

I almost feel there needs to be something in-between IR languages like LLVM IR and general-purpose C, that's not assembly but still general-purpose, functional/imperative, static analysis and able to expose math and branching state/options/differences cleanly across a variety platforms without a fugly/verbose syntax.

To make up a pseudoreligion (if it's doesn't look like your preferred Turing-complete language, sorry) at random:

     var x, y int32

     # ... assign x and y somehow here
     begin
       x = x +! y   # or x +=! y
     rescue IntegerOverflowError
       # ... int32.max + int32.max => (0xFFFFFFFF + 0xFFFFFFFF) & 0xFFFFFFFF => 0xFFFFFFFE (-2, int32)
     rescue IntegerUnderflowError
       # ... int32.min + int32.min => (0x7FFFFFFF + 0x7FFFFFFF) & 0xFFFFFFFF => 0xFFFFFFFE (-2, int32)
     end


     var s, t uint64

     # ... assign s and t somehow here
     begin
       s *=! t
     rescue IntegerOverflowError
       # ... uint64.max * uint64.max => ... => 1 (1, uint64)
     end

spc476• 12 years ago

In signed 2's compliment architectures (primarily any microprocessor made in the mid 70s or later) that has flags (some RISC based CPUs, like the MIPS, don't have individual flags) will usually have an Overflow flag, (O or V), a Carry flag (C), a Zero flag (Z) and a Sign or Negative flag (S or N---here I'll be using N and V since I have a preference for Motorola CPUs). Yes, internal, a comparison is typically done via a subtraction; the flags are updated, but not the destination register. Now, depending upon how you want to interpret the results, as a signed comparison or unsigned comparison, depends on the flags you check (and the conditional jump (or branch) instructions will do this check for you). The flags that are checked for unsigned comparison are (!f means NOT f, i.e. the flag is not set):

    above or equal: !C
    above:          !C and !Z
    below or equal: C or Z
    below:          C

And the signed comparisons are:

    above or equal: N == V
    above:          N == V and !Z
    below or equal: N != V or Z
    below:          N != V

And, just for completeness, for both signed and unsigned:

    equal:   Z
    unequal: !Z

userbinator2• 12 years ago

Because that overflag makes all the difference (no pun intended), I wouldn't say that they are the same, but that comparison usually involves subtraction.

I remember coming across a set of lecture slides for a CS course on architecture that used its own toy architecture with neither flags nor separate comparison instructions - saying that comparison is the same as subtraction gives people the entirely wrong idea, and leads to the sort of bugs mentioned in this article.

gonzo3• 12 years ago

Someone needs to explain to Teddy how the compiler implements subtraction.

Hint: his example is fine (and thus, Ted is wrong).

But, since Ted is OpenBSD.. here come the downvotes.

As the poster below states, the example in the last link of Ted's posting has overflow problems.

cremno4• 12 years ago

You should read the post again and then open the last link. Then tell us again that the example is fine.

gonzo3• 12 years ago

Last link is just someone being stupid.

imron2• 12 years ago

Doesn't seem so fine to me..

  /*compare.c*/
  #include <stdio.h>
  
  int compare( int x, int y )
  {
      return x - y;
  }
  
  void testCompare( int x, int y )
  {
      if ( compare( x, y ) < 0 )
      {
          printf( "%d is less than %d\n", x, y );
      }
      else
      {
          printf( "%d is greater than or equal to %d\n", x, y );
      }
  }
  
  int main()
  {
      testCompare( 5, 10 );
      testCompare( 10, 5 );
      testCompare( 1987654321, -1987654321 );
      return 0;
  }

$ clang -o compare compare.c

$ ./compare

5 is less than 10

10 is greater than or equal to 5

1987654321 is less than -1987654321

industriousthou• 12 years ago

I'm learning javascript, so this sort of issue doesn't really make sense to me, but I gather this is a specific issue with C and it has to do with how large integers are handled. Fair enough, but I'm actually quite curious how you should solve this kind of problem in a low level language and why.

SamReidHughes3• 12 years ago

You just write a function that returns -1, 0, or 1. It's not specific to C, it's in any language that has fixed-size types.

Another reason (a lame one) to return -1, 0, or 1 is that often the caller expects one of those return values for some reason (because the caller is dumb and your comparison function is replacing another one that behaved that way).

TwoBit2• 12 years ago

This isn't a problem with comparison by subtraction, it's a problem with integer overflow. There's nothing wrong with comparison via subtraction if you account for overflow, which you always need to do in programming.

marvy3• 12 years ago

But the only way to account for overflow is to avoid comparison by subtraction.

arielby2• 12 years ago

You can also do the comparison over larger integers, for example

  int cmp(int x, int y) {
    return (int) (((long)x-(long)y)>>32);
  }

ambrop7• 12 years ago

Just do (x>y)-(x<y). It's actually pretty fast: http://stackoverflow.com/questions/10996418/efficient-intege...

Disclaimer: not actually my original invention.

pkhuong• 12 years ago

That's a good one for integers and if you don't intend the comparator to be inlined. For inlined comparison, I prefer if (x == y) return 0; return (x < y) ? -1 : 1;. The control flow is more transparent and C compilers are usually able to perform the if/if conversion necessary to get the single comparison you'd expect in hand-rolled sorts or searches.

salmonellaeater• 12 years ago

One way to reduce the chance of this problem occurring is to change the specification of the comparison function to only allow -1, 0, and 1 to be returned (or even better, use enums like LESS, EQUAL, GREATER). This makes doing the wrong thing more cumbersome when implementing a comparison function, but it also makes it easier to implement the actual sort function because jump tables and switch statements become possibilities.

Garlef• 12 years ago

From a category theoretic point of view, subtraction is a natural candidate for comparison: It is the internal hom-functor in the ordered monoid of integers. One could argue that internal hom functors are the very essence of a "comparison".

The sole problem seems to be that integers in C are not actually integers.

emmelaich• 12 years ago

I think you're right but it goes deeper. Integers as represented in computers are not integers.

marcosdumay• 12 years ago

Nobody handles overflow in practice.

There are all kinds of code patterns that are sensitive to overflow, and people do use those patterns because they are simple. A program that does not fail on overflow is something almost illegible, and for most applications the only difference it can make is displaying the correct error message before closing, because the problem domain has no procedure for that.

C programmers are implicitly expected to estimate the value ranges they'll be dealing with, and correctly size their variables.

Subtraction is not comparison

Related Stories