Nearly All Binary Searches and Mergesorts Are Broken (2006)

Post by pishpash » Wed, Aug 02, 2017, 2:34 AM UTC

throwaway91111 wrote: post #26

albinofrenchy wrote: post #10

Earlier quoted context omitted.

Simply changing to size_t doesn't really fix this bug. You still have to use the low + (high - low) / 2 fix.

If "this bug" is the ability to sort >2^30 elements on a 64-bit machine, this bug IS addressed by changing the index type. Of course sorting 2^63 elements would require the different calculation.

Post by khedoros1 » Wed, Aug 02, 2017, 2:39 AM UTC

admax88q wrote: post #48

sillysaurus3 wrote: post #4

I wish it was worth a lot to be good at systems programming these days. It seems like the huge salaries are for rails senior devs. I spent like ten years getting really good at this stuff (the (low + high)/2 line jumped right out at me) but nowadays it feels like being really good at trivial pursuit. It's interesting how much things have changed in the last decade. I wonder what next decade's "Rails" will be? Could i…

The problem is these sorts of things are trivia. They are things that sufficiently smart tooling should handle for us so people can spend time building higher level constructs and less time worrying about individual bits. A smart compiler should have caught (a + b) / 2 and fixed it to be correct, there's no way the overflow situation is what the programmer wanted.

Post by pishpash » Wed, Aug 02, 2017, 2:59 AM UTC

SAI_Peregrinus wrote: post #6

maxton wrote: post #2

That line from the C/C++ "fix" is an atrocity; `low`, `mid`, and `high` should never have been declared as signed integers in the first place, since array indices are never negative. It's unfortunate that in Java there is no other option than to use signed ints.

For C99, the correct type for an array index is size_t. unsigned int isn't guaranteed to be big enough, while size_t is guaranteed to be large enough for the target architecture.

  #include 
  #include 
  
  int main() {
    printf("size_t bytes: %u\n", sizeof(size_t));
    
    size_t high = SIZE_MAX;
    size_t low = high-1;
    size_t mid_correct = low+(high-low)/2;
    size_t mid_incorrect = (low+high)/2;
    
    printf("low: %.ju\n", low);
    printf("high: %.ju\n", high);
    printf("low+high: %.ju\n", low+high);
    printf("(low+high)/2 -- incorrect: %.ju\n", mid_incorrect);
    printf("low+(high-low)/2 -- correct: %.ju\n", mid_correct);
  }

  size_t bytes: 8
  low: 18446744073709551614
  high: 18446744073709551615
  low+high: 18446744073709551613
  (low+high)/2 -- incorrect: 9223372036854775806
  low+(high-low)/2 -- correct: 18446744073709551614

Post by e12e » Wed, Aug 02, 2017, 3:36 AM UTC

bradleyjg wrote: post #57

e12e wrote: post #32

I'm surprised about the suggested solution for java: int mid = (low + high) >>> 1; I suppose things like this is why the ">>>" (unsigned shift) operator exists - but it's a bit odd when the value it works on is considered signed by the language, and implemented as two-compliment signed in memory. What's interesting to me is that this allows the sum to overflow, and would fail with the ">>" operator as far as I can te…

I agree it would be very surprising to see that line in a java codebase. >>> seems more like an answer to a java trivia question than something you'd come across on a regular basis.