## How to compare pairs of integers?[solved]

General FreeBASIC programming questions.
D.J.Peters
Posts: 8023
Joined: May 28, 2005 3:28
Contact:

### How to compare pairs of integers?[solved]

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
Last edited by D.J.Peters on Dec 10, 2007 7:00, edited 1 time in total.
cha0s
Posts: 5317
Joined: May 27, 2005 6:42
Location: Illinois
Contact:
I do not understand the syntax of those problems at all... "1*if"??
KristopherWindsor
Posts: 2428
Joined: Jul 19, 2006 19:17
Location: Sunnyvale, CA
Contact:
-> 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
Posts: 2998
Joined: Jan 15, 2007 20:44
Location: Australia
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
Posts: 3500
Joined: May 16, 2006 22:34
Location: USA
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,ksleep 3000counter_begin( 1000, HIGH_PRIORITY_CLASS )  if ((a=j) and (b=k)) or ((a=k) and (b=j)) then    asm nop  end ifcounter_endprint counter_cyclescounter_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 ifcounter_endprint counter_cyclessleep/'  if ((a=j) and (b=k)) or ((a=k) and (b=j)) then    asm nop  end ifmov ecx, dword ptr [ebp-16]cmp ecx, dword ptr [ebp-8]sete clshr ecx, 1sbb ecx, ecxmov esi, dword ptr [ebp-20]cmp esi, dword ptr [ebp-12]sete dlmov esi, edxshr esi, 1sbb esi, esiand ecx, esimov esi, dword ptr [ebp-20]cmp esi, dword ptr [ebp-8]sete dlmov esi, edxshr esi, 1sbb esi, esimov ebx, dword ptr [ebp-16]cmp ebx, dword ptr [ebp-12]sete blshr ebx, 1sbb ebx, ebxand esi, ebxor ecx, esije .Lt_001Bnop.Lt_001B:  if ((a XOR j) OR (b XOR k)) * ((a XOR k) OR (b XOR j)) = 0 then    asm nop  end ifmov 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, esimov 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, ebximul ecx, esitest ecx, ecxjne .Lt_0029nop.Lt_0029:'/`

Code: Select all

`5112`

A cycle count of 12 will be difficult to improve on.
RockTheSchock
Posts: 228
Joined: Mar 12, 2006 16:25

### Faster compare with asm

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

Code: Select all

`Dim As Integer a=2,b=1,j=1,k=2Screen 0  counter_begin( 1000, HIGH_PRIORITY_CLASS )   if ((a=j) and (b=k)) or ((a=k) and (b=j)) Then      asm nop   End Ifcounter_endPrint 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 Ifcounter_endPrint counter_cycles; " cycles" Dim flag as Integercounter_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 eq1neq1:   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 AsmIf flag=1 Then   asm nopEndIfcounter_endPrint counter_cycles; " cycles"sleep`
Richard
Posts: 2998
Joined: Jan 15, 2007 20:44
Location: Australia
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
Posts: 8023
Joined: May 28, 2005 3:28
Contact:
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
Posts: 1525
Joined: May 27, 2005 17:18
Contact:
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
Posts: 5317
Joined: May 27, 2005 6:42
Location: Illinois
Contact:
Or, at least

Code: Select all

`if (collison_object_1=car_class) and (collison_object_2=terain_class) thenelseif (collison_object_1=terain_class) and (collison_object_2=car_class) thenelse'it must be car car collisionend 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
Posts: 3500
Joined: May 16, 2006 22:34
Location: USA
RockTheSchock wrote: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
Posts: 6189
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs
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_thingsif (a xor b) = (j xor k) then _    if ((a=j) and (b=k)) or ((a=k) and (b=j)) then make super_thingsif (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
Posts: 155
Joined: Jan 07, 2007 17:21
D.J.Peters wrote: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...`