Thread overview | |||||
---|---|---|---|---|---|
|
October 14, 2004 old sorting error | ||||
---|---|---|---|---|
| ||||
I documented this problem long ago. It may lead to errors in sorting floating point arrays: ===================================================== April 6, 2004 === a number of floating point type arrays don't sort correctly und certain circumstances. This is the code: class TypeInfo_d : TypeInfo { ... int compare(void *p1, void *p2) { return *(double *)p1 - *(double *)p2; } ... } When values are small (I tried to sort uSecond timings like the following): sectab[0] 0.0000070792 sectab[1] 0.0000072514 sectab[2] 0.0000066818 sectab[3] 0.0000067485 sectab[4] 0.0000066986 sectab[5] 0.0000068492 sectab[6] 0.0000066601 sectab[7] 0.0000065775 sectab[8] 0.0000068234 sectab[9] 0.0000067371 sectab[10] 0.0000067350 rounding will make the return value unusable and the array remains unsorted. I think similar problems would turn up, when numbers are too large for the int range. The typical construction that you use in other places, will avoid the problem: type a = *(type *) p1; type b = *(type *) p2; return a < b ? -1 : a > b ? 1 : 0; ============================================================== Although Walter acknowledged the problem at that time, the compare code now contains casts, but is virtually unchanged and is still not working: // double class TypeInfo_d : TypeInfo { char[] toString() { return "double"; } .... int compare(void *p1, void *p2) { return cast(int)(*cast(double *)p1 - *cast(double *)p2); } ... } Don't no whether the bug crept back in or it was never corrected. -- Helmut Leitner leitner@hls.via.at Graz, Austria www.hls-software.com |
October 14, 2004 Re: old sorting error | ||||
---|---|---|---|---|
| ||||
Posted in reply to Helmut Leitner | Helmut Leitner wrote:
<snip>
> Although Walter acknowledged the problem at that time, the compare code
> now contains casts, but is virtually unchanged and is still not working:
>
> // double
>
> class TypeInfo_d : TypeInfo
> {
> char[] toString() { return "double"; }
>
> ....
>
> int compare(void *p1, void *p2)
> {
> return cast(int)(*cast(double *)p1 - *cast(double *)p2);
> }
>
> ...
> }
>
> Don't no whether the bug crept back in or it was never corrected.
It probably was never fixed.
Someone really needs to go through and sanity-check all the comparators. This comparison is only valid for character/integral types smaller than int.
I reported the problem in the typo for int, and it was fixed in the next release or two. In long, it was correct when I first discovered it. So why is double wrong?
Stewart.
|
October 14, 2004 Re: old sorting error | ||||
---|---|---|---|---|
| ||||
Posted in reply to Helmut Leitner | Helmut Leitner wrote: > ===================================================== April 6, 2004 === sorry, typo, it was ===================================================== April 6, 2003 === -- Helmut Leitner leitner@hls.via.at Graz, Austria www.hls-software.com |
Copyright © 1999-2021 by the D Language Foundation