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?
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
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.
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!
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 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
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
//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;
}
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: