PJSR: Math.median(Array) bug on Win 7 1123

[mschuster]

Hi Juan,

https://dl.dropboxusercontent.com/u/109232477/PixInsight/MathMedianBug.js

Math.median(Array) fails to produce the correct result on an array of length 8816.

Code: [Select]

data.length: 8816
data.mean: 6892.6785779911725
data.median: 4089.51507

Mathematica gives an identical mean, but a median of 7091.02 (rounded).

Here is a histogram of the data. 7091 is about right IMO.

The array is inline in the script.

I am guessing this is an off by one bug similar to Sn bug here

Please double check Math.select(int, Array) also. I rely on it too and am worried that it might have a similar problem.

I will try basing a workaround on Math.sort(Array) for now.

Mike

[mschuster]

FYI: Matrix.median() is broken in the same way also.

Mike

[Juan Conejero]

Hi Mike,

Your code gives the same result as Mathematica on a test I've just made on Linux:

data.length: 8816
data.mean: 6892.6785779911725
data.median: 7091.01807

Later today I'll try on Windows, but it would be really strange if this gives different results on different platforms. Also try with this little script:

Code: [Select]

function trivialMedian( A )
{
   A.sort( function( a, b ) { return a - b; } );
   let n2 = A.length >> 1;
   if ( A.length & 1 )
      return A[n2];
   return (A[n2] + A[n2-1])/2;
}

for ( let i = 0; i < 1000; ++i )
{
   let A = [];
   for ( let i = 0; i < 8816; ++i )
      A.push( Math.random() );
   //let A = Math.randomArray( 8816 ); // equivalent to code above
   let m1 = trivialMedian( A );
   let m2 = Math.median( A );
   if ( m1 != m2 || i == 999 )
   {
      console.writeln( format( "iteration       : %d\n"
                             + "trivialMedian() : %.16e\n"
                             + "Math.median()   : %.16e", i, m1, m2 ) );
      break;
   }
}

that compares medians computed for a large number of random arrays with a trivial method that cannot fail and Math.median().

[mschuster]

Hi Juan,

Your script gives correct results on both Win 7 1023 and Mac 10.7 1098. No failures indicated.

My script continues to fail on Win 7 1123 even after a system reboot. However my script gives correct result on Mac 10.7 1098.

On Win 7 sort() based scheme gives correct result on the particular 8816 array.

I agree it is strange to see different results on different platforms.

Mike

[Juan Conejero]

I have just made a series of tests on Windows 8.1, and this particular array gives a wrong median value (4089.51507) with Math.median(), Matrix.median() and Vector.median(). Not surprising because the three methods share the same routine to load array elements. Funny enough, if you prepend 0 and 1 to the array:


let data = [ 0, 1,
0.016266, 0.019074, 0.018753, 0.023484, 0.021546, 0.024460, 0.025620, 0.021302,
...


then the routines give the correct result (7091.01807). However, if one adds the same values at the end of the array:


...
0.020081, 0.018997, 0.018662, 0.019059, 0.019791, 0.018891, 0.018250, 0.016617, 0, 1
];

Then the routines give another wrong result (6529.0226775).

I can almost guarantee that this is a compiler bug (Visual C++ 2013). I have seen many VC++ bugs in the past, and the JavaScript engine has been particularly "good" at exposing them. I've seen really strange problems caused by VC++ "peculiarities".

Here is a modified version of the test script, which shows no problems for medians of 10000 arrays of random lengths and element values:

Code: [Select]

function trivialMedian( A )
{
   A.sort( function( a, b ) { return a - b; } );
   let n2 = A.length >> 1;
   if ( A.length & 1 )
      return A[n2];
   return (A[n2] + A[n2-1])/2;
}

#define N 10000

for ( let i = 0; i < N; ++i )
{
   let A = [];
   let n = Math.random()*16000 + 100;
   for ( let i = 0; i < n; ++i )
      A.push( Math.random() );
   //let A = Math.randomArray( n ); // equivalent to code above
   let m1 = Math.median( A );   // call this one before...
   let m2 = trivialMedian( A ); // ...because trivialMedian() modifies the array
   if ( m1 != m2 || i == N-1 )
   {
      console.writeln( format( "iteration       : %d\n"
                             + "A.length        : %d\n"
                             + "trivialMedian() : %.16e\n"
                             + "Math.median()   : %.16e", i, n, m2, m1 ) );
      break;
   }
}

However, the array that you have found always gives wrong values on Windows. Welcome to the wonderland of poor compilers written by huge multinational companies...

As soon as I return home I'll try to find a workaround to this VC++ bug. Sorry for the trouble.

[mschuster]

Hi Juan,

In 1.8.4.1171 Win7 x64 Math.median(Array) still fails to produce the correct result. Just to double check, I assume a fix was not possible?

Thanks,
Mike

[Juan Conejero]

The problem here is that, frankly, I've run out of ideas as to how to fix this. The compiler bug persists even after disabling optimizations and reorganizing the code. There is something in the code shared by these routines that VC++ 2013 cannot compile correctly. This would need a debug session to identify the problem at the assembler level, but I haven't found the time to do this.

Because of this problem and others of the same sort, I am seriously considering the possibility to switch to GCC (MinGW) on Windows. I'll see also if Visual Studio 2015 is better. Again, sorry for this issue. I'll try to get it solved in the next version.

[David Serrano]

The problem here is that, frankly, I've run out of ideas as to how to fix this. The compiler bug persists even after disabling optimizations and reorganizing the code. There is something in the code shared by these routines that VC++ 2013 cannot compile correctly. This would need a debug session to identify the problem at the assembler level, but I haven't found the time to do this.

<mode="wonderland">Well you have paid for the product, right? Can't you nag the support team?</mode> Sorry for the stupid question, just an idea .

[Juan Conejero]

you have paid for the product, right?

Good point. The problem with these things is that one has to build a reduced test case where the bug is reproducible, and this is very difficult. Anyway, I would do it for sure if I were really interested in Microsoft's C++ compiler, but I am not. Besides headaches and incompatibilities of many kinds, VC++ does not give me anything that I don't have with GCC compilers. The time required to solve the issue is much better invested in exploring a port of the Windows version to MinGW, IMHO.

[georg.viehoever]

you have paid for the product, right?

...The time required to solve the issue is much better invested in exploring a port of the Windows version to MinGW, IMHO.

MinGW also has its quirks. When I looked last, FileIO performance was rather bad.

Have a look at the Intel Compiler. On Windows, it is (almost) a drop in replacement for the VS Compiler, starts at $699, and it comes with a lot of goodies. You can try it for free... https://software.intel.com/en-us/intel-parallel-studio-xe/try-buy#buynow .

Georg