# directory-dev mailing list archives

##### Site index · List index
Message view
Top
From Emmanuel Lecharny <elecha...@gmail.com>
Subject Re: Long comparisons
Date Wed, 23 Jan 2008 13:55:28 GMT
```Ok, I did some experiments with the long comparisons. Here are the results.

What I did is that I created 4 methods, comparing long using different
algorithms :

compare1 : splits longs into two ins (low and high), and then compares
the ints transformed to long.
compare2 : uses 'if ( Math.abs( comp ) == comp )'
compare3 : uses 'if ( x - y > 0 )'
compare4 : uses David's algorithm ( 4 comparisons, depending on the
longs' sign)

I did a test with X and Y, two arrays of longs, with those values :

long[] X = new long[]{Long.MIN_VALUE, -500, -1, 0, 1, 500,
Long.MAX_VALUE};
long[] Y = new long[]{Long.MIN_VALUE, -501, -500, -499, -1, 0,
1, 499, 500, 501, Long.MAX_VALUE};

Then I compare the results of those 4 compare methods. If they all have
the same result, then I print nothing. If there is some difference, than
I dump all the results.

Here is what I get :

x - y [-1, 499] = -500
Compare1 [-1, 499] => x > y
Compare4 [-1, 499] => x > y
Compare2 [-1, 499] => x < y
Compare3 [-1, 499] => x < y
-----------------------------------------------------------------

x - y [-1, 500] = -501
Compare1 [-1, 500] => x > y
Compare4 [-1, 500] => x > y
Compare2 [-1, 500] => x < y
Compare3 [-1, 500] => x < y
-----------------------------------------------------------------

x - y [-1, 501] = -502
Compare1 [-1, 501] => x > y
Compare4 [-1, 501] => x > y
Compare2 [-1, 501] => x < y
Compare3 [-1, 501] => x < y
-----------------------------------------------------------------

x - y [-1, 9223372036854775807] = -9223372036854775808
Compare1 [-1, 9223372036854775807] => x > y
Compare4 [-1, 9223372036854775807] => x > y
Compare2 [-1, 9223372036854775807] => x > y
Compare3 [-1, 9223372036854775807] => x < y
-----------------------------------------------------------------

x - y [0, -9223372036854775808] = -9223372036854775808
Compare1 [0, -9223372036854775808] => x < y
Compare4 [0, -9223372036854775808] => x < y
Compare2 [0, -9223372036854775808] => x > y
Compare3 [0, -9223372036854775808] => x < y
-----------------------------------------------------------------

x - y [0, -501] = 501
Compare1 [0, -501] => x < y
Compare4 [0, -501] => x < y
Compare2 [0, -501] => x > y
Compare3 [0, -501] => x > y
-----------------------------------------------------------------

x - y [0, -500] = 500
Compare1 [0, -500] => x < y
Compare4 [0, -500] => x < y
Compare2 [0, -500] => x > y
Compare3 [0, -500] => x > y
-----------------------------------------------------------------

x - y [0, -499] = 499
Compare1 [0, -499] => x < y
Compare4 [0, -499] => x < y
Compare2 [0, -499] => x > y
Compare3 [0, -499] => x > y
-----------------------------------------------------------------

x - y [0, -1] = 1
Compare1 [0, -1] => x < y
Compare4 [0, -1] => x < y
Compare2 [0, -1] => x > y
Compare3 [0, -1] => x > y
-----------------------------------------------------------------

x - y [1, -501] = 502
Compare1 [1, -501] => x < y
Compare4 [1, -501] => x < y
Compare2 [1, -501] => x > y
Compare3 [1, -501] => x > y
-----------------------------------------------------------------

x - y [1, -500] = 501
Compare1 [1, -500] => x < y
Compare4 [1, -500] => x < y
Compare2 [1, -500] => x > y
Compare3 [1, -500] => x > y
-----------------------------------------------------------------

x - y [1, -499] = 500
Compare1 [1, -499] => x < y
Compare4 [1, -499] => x < y
Compare2 [1, -499] => x > y
Compare3 [1, -499] => x > y
-----------------------------------------------------------------

x - y [1, -1] = 2
Compare1 [1, -1] => x < y
Compare4 [1, -1] => x < y
Compare2 [1, -1] => x > y
Compare3 [1, -1] => x > y
-----------------------------------------------------------------

x - y [500, -501] = 1001
Compare1 [500, -501] => x < y
Compare4 [500, -501] => x < y
Compare2 [500, -501] => x > y
Compare3 [500, -501] => x > y
-----------------------------------------------------------------

x - y [500, -500] = 1000
Compare1 [500, -500] => x < y
Compare4 [500, -500] => x < y
Compare2 [500, -500] => x > y
Compare3 [500, -500] => x > y
-----------------------------------------------------------------

x - y [500, -499] = 999
Compare1 [500, -499] => x < y
Compare4 [500, -499] => x < y
Compare2 [500, -499] => x > y
Compare3 [500, -499] => x > y
-----------------------------------------------------------------

x - y [500, -1] = 501
Compare1 [500, -1] => x < y
Compare4 [500, -1] => x < y
Compare2 [500, -1] => x > y
Compare3 [500, -1] => x > y
-----------------------------------------------------------------

x - y [9223372036854775807, -1] = -9223372036854775808
Compare1 [9223372036854775807, -1] => x < y
Compare4 [9223372036854775807, -1] => x < y
Compare2 [9223372036854775807, -1] => x > y
Compare3 [9223372036854775807, -1] => x < y
*********************************************************

As you can see, only methods 1 and 4 are correct. Which one should we use ?

I run the very same tests million of times, and measured the time it cost :

Delta compare 1 = 12621ms
Delta compare 2 = 12522 ms
Delta compare 3 = 10086 ms
Delta compare 4 = 7098 ms

Clearly, David's method is the best. So be it...

Thanks David !

PS: The code ...

public class TestCompareLong
{

private static int compare1( long l1, long l )
{
long l1l = l1 & 0x00000000FFFFFFFFL;
long l1h = (l1 >> 32) & 0x00000000FFFFFFFFL;

long lll = l & 0x00000000FFFFFFFFL;
long llh = (l >> 32) & 0x00000000FFFFFFFFL;

if ( l1h < llh )
{
return -1;
}
else if ( l1h > llh )
{
return 1;
}
else
{
if ( l1l < lll )
{
return -1;
}
else if ( l1l > lll )
{
return 1;
}
else
{
return 0;
}
}
}

private static int compare2( long l1, long l )
{
if ( l1 == l )
{
return 0;
}

long comp = l1 - l;

if ( Math.abs( comp ) == comp )
{
return 1;
}
else
{
return -1;
}
}

private static int compare3( long l1, long l )
{
if ( l1 == l )
{
return 0;
}

if ( l1 - l > 0 )
{
return 1;
}
else
{
return -1;
}
}

private static int compare4( long l1, long l2 )
{
if ( l1 == l2 )
{
return 0;
}

if ( l1 >= 0 )
{
if ( l2 >= 0 )
{
return ( l1 > l2 ) ? 1 : -1;
}
else
{
return -1;
}
}
else if ( l2 >= 0 )
{
return 1;
}
else
{
return ( l1 < l2 ) ? -1 : 1;
}
}

private static void test( long l1 )
{
long[] LL = new long[]{Long.MIN_VALUE, -500, -1, 0, 1, 500,
Long.MAX_VALUE};

System.out.println( "================================\n" );

for ( long l:LL )
{
if ( compare1( l1, l ) == -1 )
{
System.out.println( l1 + " > " + l );
}
else if ( compare1( l1, l ) == 1 )
{
System.out.println( l1 + " > " + l );
}
else
{
System.out.println( l1 + " = " + l );
}
}
}

private static String printResult( int value )
{
if ( value == 1 )
{
return "x > y";
}
else if ( value == -1 )
{
return "x < y";
}
else
{
return "x = y";
}
}

private static void test2()
{
long[] X = new long[]{Long.MIN_VALUE, -500, -1, 0, 1, 500,
Long.MAX_VALUE};
long[] Y = new long[]{Long.MIN_VALUE, -501, -500, -499, -1, 0,
1, 499, 500, 501, Long.MAX_VALUE};

System.out.println( "================================\n" );
for ( long x:X )
{
for ( long y:Y )
{
int res1 = compare1( x, y );
int res2 = compare2( x, y );
int res3 = compare3( x,y );
int res4 = compare4( x,y );

if ( ( res1 != res2 ) || ( res1 != res3 )|| ( res1 !=
res4 ) )
{
System.out.println(
"-----------------------------------------------------------------\n" );
System.out.println( "x - y [" + x + ", " + y +"] = "
+ ( x - y ) );
System.out.println( "Compare1 [" + x + ", " + y +"]
=> " + printResult( res1 ) );
System.out.println( "Compare4 [" + x + ", " + y +"]
=> " + printResult( res4 ) );
System.out.println( "Compare2 [" + x + ", " + y +"]
=> " + printResult( res2 ) );
System.out.println( "Compare3 [" + x + ", " + y +"]
=> " + printResult( res3 ) );
}
}
}
}

/**
*/
public static void main( String[] args )
{
test2();

System.out.println(
"*********************************************************\n" );

test( Long.MIN_VALUE );
test( -100L );
test( -1L );
test( 0L );
test( 1L );
test( 100L );
test( Long.MAX_VALUE );

int res = 0;
long t0 = System.currentTimeMillis();

for ( long i = 0; i < 2000000000L; i++ )
{
res = compare1( Long.MIN_VALUE, i );
}

long t1 = System.currentTimeMillis();

if ( res != 1 )
{
System.out.println( "Error" );
}
System.out.println( "Delta compare 1 = " + ( t1 - t0 ) );

t0 = System.currentTimeMillis();

for ( long i = 0; i < 2000000000L; i++ )
{
res = compare2( Long.MIN_VALUE, i );
}

t1 = System.currentTimeMillis();

if ( res != 1 )
{
System.out.println( "Error" );
}
System.out.println( "Delta compare 2 = " + ( t1 - t0 ) );

t0 = System.currentTimeMillis();

for ( long i = 0; i < 2000000000L; i++ )
{
res = compare3( Long.MIN_VALUE, i );
}

t1 = System.currentTimeMillis();

if ( res != 1 )
{
System.out.println( "Error" );
}
System.out.println( "Delta compare 3 = " + ( t1 - t0 ) );

t0 = System.currentTimeMillis();

for ( long i = 0; i < 2000000000L; i++ )
{
res = compare4( Long.MIN_VALUE, i );
}

t1 = System.currentTimeMillis();

if ( res != 1 )
{
System.out.println( "Error" );
}
System.out.println( "Delta compare 4 = " + ( t1 - t0 ) );
}

}

--
--
cordialement, regards,
Emmanuel Lécharny
www.iktek.com
directory.apache.org

```
Mime
View raw message