www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - old sorting error

reply Helmut Leitner <helmut.leitner wikiservice.at> writes:
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
Oct 14 2004
next sibling parent Stewart Gordon <smjg_1998 yahoo.com> writes:
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.
Oct 14 2004
prev sibling parent Helmut Leitner <helmut.leitner wikiservice.at> writes:
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
Oct 14 2004