News for hackers. Stuff that matters.
Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by Groxx on Wednesday February 17, 2010 @01:01AM (#1130977)
So, the bug is that you're overflowing integer datatypes? It's a bug that doesn't exist if your data never exceeds 1/2 of your integer value. And with 64-bit, it's effectively impossible for this to happen (except in exceedingly excessive circumstances, and then you better not be using such limited primitives, or suffer the consequences).

I mean, heck. On equal footing, you san say that it's a "bug" that you can't access array indices past what your integer can refer to, but you could conceivably push data in further than that if your array implementation allows it. The article's bug happens at 1/2 that limit, but it's the same thing, just slightly harder to find. Slightly, mind you, as something like this should be checked any time you approach the limits of your formats.

Here's something to ask: which are broken? Example code, code made for a use significantly below 2^31 values, or code in use in cases which may exceed this value? I'd be willing to bet it's the first and second. If you're not making a truly generic algorithm, don't make a generic algorithm. YAGNI.

Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by sparky on Wednesday February 17, 2010 @03:03AM (#1131127)
Nit: ints are still 32 bits on most 64-bit systems ( http://en.wikipedia.org/wiki/64-bit#Specific_data_models )

Example:

  mrj10@mjlap:~$ uname -m
  x86_64
  mrj10@mjlap:~$ cat test.c
  #include <stdio.h>
  int main()
  {
    printf("%zu\n",sizeof(int));
    return 0;  
  }
  mrj10@mjlap:~$ gcc test.c -o test
  mrj10@mjlap:~$ ./test
  4
Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by Groxx on Wednesday February 17, 2010 @05:48AM (#1131278)
Hah, yep, does the same on mine. Oh well. Thanks for the info. Long int gives me 8, but I see that the standard only requires 4 minimum, so I guess you can't rely on that either...

Eh. I'll still stick with infinite Integers if I'm worried about running out of space.

Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by jedbrown on Wednesday February 17, 2010 @07:32AM (#1131377)
> I see that the standard only requires 4 minimum

Oh really? What standard? C99 section 5.2.4.2.1 says 16 bits minimum for int, 32 bits for long, 64 for long long. There may not exist 64-bit architectures with 16-byte ints, but that's not prevented by the standard.

Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by Groxx on Wednesday February 17, 2010 @07:52AM (#1131398)
I just pulled from here, no idea if there's something more accurate: http://en.wikipedia.org/wiki/Long_integer
Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by jedbrown on Wednesday February 17, 2010 @08:02AM (#1131408)
Sorry, I misread comment. Long ints have a 4-byte minimum, plaint ints have a 2-byte minimum.
Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by maurycy on Wednesday February 17, 2010 @05:39AM (#1131267)
They're Google. Their data set is bigger than your. :-)