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]

Postby D.J.Peters » Dec 07, 2007 4:28

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
Site Admin
Posts: 5317
Joined: May 27, 2005 6:42
Location: Illinois
Contact:

Postby cha0s » Dec 07, 2007 7:23

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:

Postby KristopherWindsor » Dec 07, 2007 7:36

-> 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

Postby Richard » Dec 07, 2007 9:15

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

Postby MichaelW » Dec 07, 2007 10:13

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
Posts: 228
Joined: Mar 12, 2006 16:25

Faster compare with asm

Postby RockTheSchock » Dec 07, 2007 13:38

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
Posts: 2998
Joined: Jan 15, 2007 20:44
Location: Australia

Postby Richard » Dec 07, 2007 14:32

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:

Postby D.J.Peters » Dec 07, 2007 16:34

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
Posts: 1525
Joined: May 27, 2005 17:18
Contact:

Postby jofers » Dec 07, 2007 18:06

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
Site Admin
Posts: 5317
Joined: May 27, 2005 6:42
Location: Illinois
Contact:

Postby cha0s » Dec 07, 2007 20:37

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
Posts: 3500
Joined: May 16, 2006 22:34
Location: USA

Postby MichaelW » Dec 07, 2007 22:01

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
Site Admin
Posts: 6189
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

Postby counting_pine » Dec 08, 2007 11:05

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
Posts: 155
Joined: Jan 07, 2007 17:21

Postby Tigra » Dec 08, 2007 14:20

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...

Return to “General”

Who is online

Users browsing this forum: No registered users and 5 guests