How to compare pairs of integers?[solved]

[D.J.Peters]

all are integer class ID's

if ((a=j) and (b=k)) or ((a=k) and (b=j)) then make super_things

1*if + 4*= + 2*AND + 1*OR = 8

how can i use XOR to make it shorter/faster

i was thinking
test1=(a=j):test2=(b=k)
if test1 XOR test2 then make_super_things

1*if + 4*= + 1*XOR = 6

what are wrong with this construct and what is shorter/faster?

Joshy

[cha0s]

I do not understand the syntax of those problems at all... "1*if"??

[KristopherWindsor]

-> if ((a=j) and (b=k)) or ((a=k) and (b=j)) then make super_things

That seems about as fast as you can get it, unless you know something else about the variables.
The code "test1=(a=j):test2=(b=k): if test1 XOR test2 then make_super_things" is completely different, because it might just mean a = j, which can be true no matter what values b and k are.

[Richard]

XOR sets the bits that are different so it can be used to do the comparisons but not to replace the middle AND in your expression.
When (a=j) becomes (a XOR j) then all bits in the result will be zero only if a=j .
((a=j) and (b=k)) becomes(a XOR j) OR (b XOR k), because of the negative logic. Likewise ((a=k) and (b=j)) becomes((a XOR k) OR (b XOR j)), the OR function preserves the differing bits.
Now we need to test if either of these terms is zero. Unfortunately we cannot use AND because the bits that differed may not be in the same places. To use AND we would need to flood the inputs with “one”s if any “one” is present but it would probably be easier simply to test for zero, twice if necessary.

Alternatively test ((a XOR j) OR (b XOR k)) * ((a XOR k) OR (b XOR j)) for zero. The multiply will return zero if either side is zero.

[MichaelW]

I would have guessed that the version with the multiply would have been somewhat slower, but on my P3 it’s much faster.

Code: Select all

'====================================================================
#include "windows.bi"
#include "counter.bas"
'====================================================================
'' Counter.bas is available here:
''
'' http://www.freebasic.net/forum/viewtopic.php?t=4221
'====================================================================

dim as integer a,b,j,k

sleep 3000

counter_begin( 1000, HIGH_PRIORITY_CLASS )
  if ((a=j) and (b=k)) or ((a=k) and (b=j)) then
    asm nop
  end if
counter_end
print counter_cycles

counter_begin( 1000, HIGH_PRIORITY_CLASS )
  if ((a XOR j) OR (b XOR k)) * ((a XOR k) OR (b XOR j)) = 0 then
    asm nop
  end if
counter_end
print counter_cycles

sleep


/'
  if ((a=j) and (b=k)) or ((a=k) and (b=j)) then
    asm nop
  end if

mov ecx, dword ptr [ebp-16]
cmp ecx, dword ptr [ebp-8]
sete cl
shr ecx, 1
sbb ecx, ecx
mov esi, dword ptr [ebp-20]
cmp esi, dword ptr [ebp-12]
sete dl
mov esi, edx
shr esi, 1
sbb esi, esi
and ecx, esi
mov esi, dword ptr [ebp-20]
cmp esi, dword ptr [ebp-8]
sete dl
mov esi, edx
shr esi, 1
sbb esi, esi
mov ebx, dword ptr [ebp-16]
cmp ebx, dword ptr [ebp-12]
sete bl
shr ebx, 1
sbb ebx, ebx
and esi, ebx
or ecx, esi
je .Lt_001B
nop
.Lt_001B:

  if ((a XOR j) OR (b XOR k)) * ((a XOR k) OR (b XOR j)) = 0 then
    asm nop
  end if

mov ecx, dword ptr [ebp-16]
xor ecx, dword ptr [ebp-8]
mov esi, dword ptr [ebp-20]
xor esi, dword ptr [ebp-12]
or ecx, esi
mov esi, dword ptr [ebp-20]
xor esi, dword ptr [ebp-8]
mov ebx, dword ptr [ebp-16]
xor ebx, dword ptr [ebp-12]
or esi, ebx
imul ecx, esi
test ecx, ecx
jne .Lt_0029
nop
.Lt_0029:

'/

Code: Select all

51
12

A cycle count of 12 will be difficult to improve on.

[RockTheSchock]

On my p3 my version runs faster:
cycles 49 - 16 - 13

Code: Select all

Dim As Integer a=2,b=1,j=1,k=2
Screen 0

  

counter_begin( 1000, HIGH_PRIORITY_CLASS )
	if ((a=j) and (b=k)) or ((a=k) and (b=j)) Then
		asm nop
	End If
counter_end

Print counter_cycles; " cycles"



counter_begin( 1000, HIGH_PRIORITY_CLASS )
  If ((a Xor j) Or (b Xor k)) * ((a Xor k) Or (b Xor j)) = 0 Then
    asm nop
  End If
counter_end
Print counter_cycles; " cycles"





 
Dim flag as Integer


counter_begin( 1000, HIGH_PRIORITY_CLASS )

Asm

	
	mov eax,[a]
	mov ebx,[j]
	cmp eax,ebx
	jne neq1
	
	
	mov eax,[b]
	mov ebx,[k]
	cmp eax,ebx
	je eq1

neq1:
	mov eax,[a]
	mov ebx,[k]
	cmp eax,ebx
	jne neq2
	
	
	mov eax,[b]
	mov ebx,[j]
	cmp eax,ebx
	jne neq2
	
eq1:
	mov eax,1
	mov [flag],eax
	
neq2:
End Asm

If flag=1 Then
	asm nop
EndIf
counter_end


Print counter_cycles; " cycles"




sleep

[Richard]

Cryptic syntax? “ 1*if + 4*= + 2*AND + 1*OR = 8 “ can be interpreted as:
One “If”, plus four “equalities”, plus two “ANDs”, plus one “OR” gives eight operations total.

[D.J.Peters]

thanx for your tip's
i need it very often (1000*100fps) per second

if (collison_object_1=car_class) and (collison_object_2=terain_class) or
(collison_object_1=terain_class) and (collison_object_2=car_class) then
else
'it must be car car collision
end if

[jofers]

For the sake of readable code, I would leave it the way it was, since micro-optimizations are only going to buy you a few cycles at best and is pretty hardware-dependent. Instead, see what your program's spending the most time doing and concentrate on improving that.

[cha0s]

Or, at least

Code: Select all

if (collison_object_1=car_class) and (collison_object_2=terain_class) then
elseif (collison_object_1=terain_class) and (collison_object_2=car_class) then
else
'it must be car car collision
end if

Ok Richard, I get that it was an "equation" for like orders of complexity. I was looking at it like a value-returning expression and wondering how to solve it :P

IF(1) + =(4) + AND(2) + OR(1) is one way it looks a bit clearer to me, why nitpick though, everyone else understood the original way, yes?

[MichaelW]

On my p3 my version runs faster:
cycles 49 - 16 - 13

I was assuming that the goal was to do it without asm. Ignoring the final comparison, the first two versions have only one possible execution path, so the cycle count is independent of the inputs. Your version has three possible execution paths, the best case being when a=j and b=k, and the worst case when a=j, b<>k, and a=k. Running under Windows the cycle counts for your code varies much more than it does for the first two versions, so by averaging the cycle counts over multiple trials I get a worst case cycle count of ~8 and a best case of ~5. Also, your code contains some unnecessary instructions. To compare two memory variables only one of them must be in a register, so for example the first 4 instructions could be reduced to:

Code: Select all

mov eax, [a]
cmp eax, [j]
jne L1

[counting_pine]

Looking at the problem from another angle:

Is it a rare-ish case you're testing for? If so, maybe it's possible to do a test that can give false positives, but is faster. If it passes that test, then you can do a more comprehensive one.

If (a,b) = (j,k) or (k,j) then you know that, for a symmetric function f:

f(a, b) = f(j, k)

Simple symmetric functions include: (a+b), (a*b), (a or b), (a xor b), abs(a-b).
Some will be slower than others, and depending on the situation, some will give more false positives than others, so there's a bit of room for compromise.

But anyway, a couple of examples to illustrate:

Code: Select all

if (a + b) = (j + k) then _
    if ((a=j) and (b=k)) or ((a=k) and (b=j)) then make super_things

if (a xor b) = (j xor k) then _
    if ((a=j) and (b=k)) or ((a=k) and (b=j)) then make super_things

if (a xor b xor j xor k) = 0 then _
    if ((a=j) and (b=k)) or ((a=k) and (b=j)) then make super_things

The first example will give false positive whenever the midpoints of a--b, and j--k coincide, but their distances differ, which (depending on the situation) might be quite common.

The second and third examples are equivalent. They might yield false positives in a less predictable manner, which might be good. Probably worthy of note, though, is that it's completely symmetric throughout all four values. So if you swap, say, b and j, the test will give the same result.

So anyway, an easy preliminary test might give a speedup, but it would be worth putting some thought into what test to use.

[Tigra]

if (collison_object_1=car_class) and (collison_object_2=terain_class) or
(collison_object_1=terain_class) and (collison_object_2=car_class) then
else
'it must be car car collision
end if

I am curious what the data types involved are? If all are int's AND car_class and terain_class have distinct bit's, would something like this work?

Code: Select all

if ( collison_object_1 and (car_class Or terain_class) ) Or ( collison_object_2 and (car_class Or terain_class) ) Then...