31–40 of 51 posts
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 ac…
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 ac…
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 int main() { printf("%zu\n",sizeof(int)); return 0; } mrj10@mjlap:~$ gcc test.c -o test mrj10@mjlap:~$ ./test 4
Eh. I'll still stick with infinite Integers if I'm worried about running out of space.
I remember reading this (back in 2006?) and looking at the versions of Binary Search and Merge Sort that I had recently written for the Data Structures & Algorithms class that I teach. I found that my versions did not have this bug, despite the fact that I had not given any thought to it. The reason my code did not have the bug is that I represented the range to be processed, not as low & high subscripts, but rather…
It seems to me that this "fix" just pushes the bug off by a factor of 2. What happens when you have an array with more elements than can be expressed by an int? I also question the mergesort assertion. I've implemented mergesort several times, almost always expressed in terms of writing to/from pipes of data (that under the hood eventually wound up going to disk I/O in some way). Those solutions will not suffer from…
This contrasts with the overflow defect which would cause the mergesort routine to fail when given an otherwise perfectly valid input.
Earlier quoted context omitted.
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 int main() { printf("%zu\n",sizeof(int)); return 0; } mrj10@mjlap:~$ gcc test.c -o test mrj10@mjlap:~$ ./test 4
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.
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.
It seems to me that this "fix" just pushes the bug off by a factor of 2. What happens when you have an array with more elements than can be expressed by an int? I also question the mergesort assertion. I've implemented mergesort several times, almost always expressed in terms of writing to/from pipes of data (that under the hood eventually wound up going to disk I/O in some way). Those solutions will not suffer from…
> What happens when you have an array with more elements than can be expressed by an int? You probably couldn't have an array that big and even if you could, it's likely this function would accept it at compile time. The problem here is that you're passing it an array that it is advertised to handle, yet it fails.
Earlier quoted context omitted.
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.
> 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.
Earlier quoted context omitted.
> 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.
I just pulled from here, no idea if there's something more accurate: http://en.wikipedia.org/wiki/Long_integer