Sticky logic problem

Discussion of chess software programming and technical issues.

Moderator: Ras

Michael Sherwin
Posts: 3196
Joined: Fri May 26, 2006 3:00 am
Location: WY, USA
Full name: Michael Sherwin

Sticky logic problem

Post by Michael Sherwin »

While chess programming I keep encountering the following logic construct which seems as though it could be done much more efficiently than the natural code that follows. However, whenever I try to improve it, it seems that I almost have it, but always I end up so confused that my attempt falls apart. Anyone feel like taking a shot at it?

Code: Select all

if(a == b) {
    if(c < d) {
        if(e > f) g += h;
    } else {
        if(e < f) g += h;
    }
} else {
    if(c < d) {
        if(e < f) g += h;
    } else {
        if(e > f) g += h;
    }
}
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
CRoberson
Posts: 2091
Joined: Mon Mar 13, 2006 2:31 am
Location: North Carolina, USA

Re: Sticky logic problem

Post by CRoberson »

Looks to me like it reduces to
g+= h
User avatar
xsadar
Posts: 147
Joined: Wed Jun 06, 2007 10:01 am
Location: United States
Full name: Mike Leany

Re: Sticky logic problem

Post by xsadar »

it looks to me like it reduces to:

Code: Select all

if (c < d && e != f)
  g += h;
even still I doubt that's what was intended
User avatar
hgm
Posts: 28353
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Sticky logic problem

Post by hgm »

The two remarks above are not correct.

Ii e == f you never do anything. Otherwise, it is an exclusive-or construct: you add to g if

(a==b) ^ (c<d) ^ (e>f)

So the conditions under which you add are

(e!=f) & ((a==b) ^ (c<d) ^ (e>f))

This expression is 1 if you want to add, zero otherwise. So you can finally write

g += h & -((e!=f) & ((a==b) ^ (c<d) ^ (e>f)));

as -1 is an all-ones pattern that ANDed with h leaves it unchanged, and ANDing with 0 kills h completely.

This gives you a nice branchless translation. If you know beforehand that e and f cannot be equal, (or if the condition e<f should really be e<=f in your initial problem) you could of course leave out the (e!=f) factor.
Michael Sherwin
Posts: 3196
Joined: Fri May 26, 2006 3:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: Sticky logic problem

Post by Michael Sherwin »

hgm wrote:The two remarks above are not correct.

Ii e == f you never do anything. Otherwise, it is an exclusive-or construct: you add to g if

(a==b) ^ (c<d) ^ (e>f)

So the conditions under which you add are

(e!=f) & ((a==b) ^ (c<d) ^ (e>f))

This expression is 1 if you want to add, zero otherwise. So you can finally write

g += h & -((e!=f) & ((a==b) ^ (c<d) ^ (e>f)));

as -1 is an all-ones pattern that ANDed with h leaves it unchanged, and ANDing with 0 kills h completely.

This gives you a nice branchless translation. If you know beforehand that e and f cannot be equal, (or if the condition e<f should really be e<=f in your initial problem) you could of course leave out the (e!=f) factor.
Wonderful, that is the kind of thing that I was looking for. Thanks! :D
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Michael Sherwin
Posts: 3196
Joined: Fri May 26, 2006 3:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: Sticky logic problem

Post by Michael Sherwin »

CRoberson wrote:Looks to me like it reduces to
g+= h
Lets say that a equals b; the first ifs true clause is executed.

Lets say that c is less than d; then the second ifs clause is executed.

Then if e is not greater than f then nothing happens!
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Michael Sherwin
Posts: 3196
Joined: Fri May 26, 2006 3:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: Sticky logic problem

Post by Michael Sherwin »

xsadar wrote:it looks to me like it reduces to:

Code: Select all

if (c < d && e != f)
  g += h;
even still I doubt that's what was intended
I think that you are right Mike. This is now not looking like I intended.

The if a == b makes no sense if followed by the same if c < d and h gets added on inequality in either case.

I will see what the original problem was and post a corrected version.

Thanks
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Chan Rasjid
Posts: 588
Joined: Thu Mar 09, 2006 4:47 pm
Location: Singapore

Re: Sticky logic problem

Post by Chan Rasjid »

Hello,

Code: Select all

//your code
if(a == b) {
    if (c < d) {
        if (e > f) g += h;
    } else {
        if (e < f) g += h;
    }
} else {
    if (c < d) {
        if (e < f) g += h;
    } else {
        if (e > f) g += h;
    }
}
//should be <==>
  
    if (c < d) {
        if(e != f) g += h;
    } else {
        if(e != f) g += h;
    }
//should be <==>
 
    if (e != f) g += h;

} 
Answer :-
if (e != f) g += h;

Rasjid
Gerd Isenberg
Posts: 2251
Joined: Wed Mar 08, 2006 8:47 pm
Location: Hattingen, Germany

Re: Sticky logic problem

Post by Gerd Isenberg »

hgm wrote:The two remarks above are not correct.

Ii e == f you never do anything. Otherwise, it is an exclusive-or construct: you add to g if

(a==b) ^ (c<d) ^ (e>f)

So the conditions under which you add are

(e!=f) & ((a==b) ^ (c<d) ^ (e>f))

This expression is 1 if you want to add, zero otherwise. So you can finally write

g += h & -((e!=f) & ((a==b) ^ (c<d) ^ (e>f)));

as -1 is an all-ones pattern that ANDed with h leaves it unchanged, and ANDing with 0 kills h completely.

This gives you a nice branchless translation. If you know beforehand that e and f cannot be equal, (or if the condition e<f should really be e<=f in your initial problem) you could of course leave out the (e!=f) factor.
While your solution is perfectly ok, the minor drawback are the flag-dependencies of the four setXX-instructions. Assuming the most significant bit of {a,b,c,d,e,f} is always clear, using sub instead of cmp and sar 31 instead of setCC may gain more paralellism and leaves {-1,0} masks:

Code: Select all

int aEQb, cLSd, eGRf, eLSf;
aEQb   = (a^b)-1;
cLSd   = c - d;
eGRf   = f - e;
eLSf   = e - f;
aEQb >>= 31; // -1 if a == b, otherwise 0
cLSd >>= 31; // -1 if c < d, otherwise 0
eGRf >>= 31; // -1 if e > f, otherwise 0
eLSf >>= 31; // -1 if e < f, otherwise 0
g += h & (eGRf ^ eLSf) & (aEQb ^ cLSd ^ eGRf); 
rjgibert
Posts: 317
Joined: Mon Jun 26, 2006 9:44 am

Re: Sticky logic problem

Post by rjgibert »

g += h & -(e!=f) should look familiar to you. It's your original solution sans all the redundancies you appended.

BTW, it doesn't seem to be equivalent to your solution. I'll have to think about it later, but seems your original solution may be incorrect.