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
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.