[math-fun] absolute value (branchless)
suppose my computer wants |x| but it refuses to perform an "if" statement. What to do?
Assuming x is a 32-bit integer, here's one way that uses 3 instructions: int y = x >> 31; int negx = (x ^ y) - y; J.P. On Fri, Aug 23, 2013 at 4:25 PM, Warren D Smith <warren.wds@gmail.com>wrote:
suppose my computer wants |x| but it refuses to perform an "if" statement.
What to do?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
(typo: that should read 'absx', not 'negx') On Fri, Aug 23, 2013 at 4:44 PM, J.P. Grossman <jpg@alum.mit.edu> wrote:
Assuming x is a 32-bit integer, here's one way that uses 3 instructions:
int y = x >> 31; int negx = (x ^ y) - y;
J.P.
On Fri, Aug 23, 2013 at 4:25 PM, Warren D Smith <warren.wds@gmail.com>wrote:
suppose my computer wants |x| but it refuses to perform an "if" statement.
What to do?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
well, let's try that... x = 1 y = 0 x^y = 1 x^y - y = 0 On 2013-08-23 16:45, J.P. Grossman wrote:
(typo: that should read 'absx', not 'negx')
On Fri, Aug 23, 2013 at 4:44 PM, J.P. Grossman <jpg@alum.mit.edu> wrote:
Assuming x is a 32-bit integer, here's one way that uses 3 instructions:
int y = x >> 31; int negx = (x ^ y) - y;
J.P.
On Fri, Aug 23, 2013 at 4:25 PM, Warren D Smith <warren.wds@gmail.com>wrote:
suppose my computer wants |x| but it refuses to perform an "if" statement.
What to do?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
OOPS. Last line should clearly be x^y-y=1 So, it seems to work. Negatives do a 1-s complement and then add 1. Positives don't change. SOunds good to me. --ms On 2013-08-23 16:54, Mike Speciner wrote:
well, let's try that... x = 1 y = 0 x^y = 1 x^y - y = 0
On 2013-08-23 16:45, J.P. Grossman wrote:
(typo: that should read 'absx', not 'negx')
On Fri, Aug 23, 2013 at 4:44 PM, J.P. Grossman <jpg@alum.mit.edu> wrote:
Assuming x is a 32-bit integer, here's one way that uses 3 instructions:
int y = x >> 31; int negx = (x ^ y) - y;
J.P.
On Fri, Aug 23, 2013 at 4:25 PM, Warren D Smith <warren.wds@gmail.com>wrote:
suppose my computer wants |x| but it refuses to perform an "if" statement.
What to do?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The last one is wrong: (x^y) - y = (1^0) - 0 = 1 - 0 = 1 Tom Mike Speciner writes:
well, let's try that... x = 1 y = 0 x^y = 1 x^y - y = 0
On 2013-08-23 16:45, J.P. Grossman wrote:
(typo: that should read 'absx', not 'negx')
On Fri, Aug 23, 2013 at 4:44 PM, J.P. Grossman <jpg@alum.mit.edu> wrote:
Assuming x is a 32-bit integer, here's one way that uses 3 instructions:
int y = x >> 31; int negx = (x ^ y) - y;
J.P.
On Fri, Aug 23, 2013 at 4:25 PM, Warren D Smith <warren.wds@gmail.com>wrote:
suppose my computer wants |x| but it refuses to perform an "if" statement.
What to do?
* J.P. Grossman <jpg@alum.mit.edu> [Aug 24. 2013 08:11]:
Assuming x is a 32-bit integer, here's one way that uses 3 instructions:
int y = x >> 31;
Here you assume that the sign bit gets spread out. IIRC the C standard does not guarantee this ("arithmetic right shift"). Cf. fxtbook, section "1.11 Avoiding branches" p.25ff for a selection of such tricks. The section contains one bad error that has not been documented in the errata. Where is it? Best, jj
int negx = (x ^ y) - y;
J.P.
On Fri, Aug 23, 2013 at 4:25 PM, Warren D Smith <warren.wds@gmail.com>wrote:
suppose my computer wants |x| but it refuses to perform an "if" statement.
What to do?
[...]
Well you could always do y = x&(1<<31); y |= (y>>1)|(y>>2)|...|(y>>31); // all this just to avoid an if which probably costs nothing while the processor does both possibilities in parallel ? (And of course this all assume 32-bit integers.) But the original question wasn't about C, it was about "your computer". [jpg was presumably just using C notation for exposition.] And of course, then it depends on what the instruction set has in it, which wasn't specified. Also what wasn't specfied was whether x was fixed or floating point, or even what number formats the processor natively uses. If the format is sign/magnitude (which I believe the IEEE binary floating point standard is), the problem gets easier. By the way, if you want to have overflow detected, then instead of x^y - y, use x*(y*2+1). --ms On 24-Aug-13 02:31, Joerg Arndt wrote:
* J.P. Grossman <jpg@alum.mit.edu> [Aug 24. 2013 08:11]:
Assuming x is a 32-bit integer, here's one way that uses 3 instructions:
int y = x >> 31; Here you assume that the sign bit gets spread out. IIRC the C standard does not guarantee this ("arithmetic right shift").
Cf. fxtbook, section "1.11 Avoiding branches" p.25ff for a selection of such tricks. The section contains one bad error that has not been documented in the errata. Where is it?
Best, jj
int negx = (x ^ y) - y;
J.P.
On Fri, Aug 23, 2013 at 4:25 PM, Warren D Smith <warren.wds@gmail.com>wrote:
suppose my computer wants |x| but it refuses to perform an "if" statement.
What to do?
[...]
math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
* Mike Speciner <ms@alum.mit.edu> [Aug 24. 2013 18:39]:
Well you could always do y = x&(1<<31); y |= (y>>1)|(y>>2)|...|(y>>31); // all this just to avoid an if which probably costs nothing
With pipelining an "if" (a conditional branch) can be expensive. There are situations where these tricks can give a notable boost in performance.
[...]
Best, jj
gcc uses this trick: solarium:~ rokicki$ cat t.c int mabs(int x) { if (x < 0) return -x ; return x ; } solarium:~ rokicki$ gcc -O5 -S t.c solarium:~ rokicki$ cat t.s ... _mabs: Leh_func_begin1: pushq %rbp Ltmp0: movq %rsp, %rbp Ltmp1: movl %edi, %ecx sarl $31, %ecx addl %ecx, %edi movl %edi, %eax xorl %ecx, %eax popq %rbp ret ... On Sat, Aug 24, 2013 at 7:39 AM, Mike Speciner <ms@alum.mit.edu> wrote:
Well you could always do y = x&(1<<31); y |= (y>>1)|(y>>2)|...|(y>>31); // all this just to avoid an if which probably costs nothing while the processor does both possibilities in parallel ? (And of course this all assume 32-bit integers.)
But the original question wasn't about C, it was about "your computer". [jpg was presumably just using C notation for exposition.] And of course, then it depends on what the instruction set has in it, which wasn't specified. Also what wasn't specfied was whether x was fixed or floating point, or even what number formats the processor natively uses. If the format is sign/magnitude (which I believe the IEEE binary floating point standard is), the problem gets easier.
By the way, if you want to have overflow detected, then instead of x^y - y, use x*(y*2+1).
--ms
On 24-Aug-13 02:31, Joerg Arndt wrote:
* J.P. Grossman <jpg@alum.mit.edu> [Aug 24. 2013 08:11]:
Assuming x is a 32-bit integer, here's one way that uses 3 instructions:
int y = x >> 31;
Here you assume that the sign bit gets spread out. IIRC the C standard does not guarantee this ("arithmetic right shift").
Cf. fxtbook, section "1.11 Avoiding branches" p.25ff for a selection of such tricks. The section contains one bad error that has not been documented in the errata. Where is it?
Best, jj
int negx = (x ^ y) - y;
J.P.
On Fri, Aug 23, 2013 at 4:25 PM, Warren D Smith <warren.wds@gmail.com>wrote:
suppose my computer wants |x| but it refuses to perform an "if" statement.
What to do?
[...]
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
Years ago (2005 I think) I entered an enhancement request into the GCC bugzilla asking for the use of the "conditional move" statement(s) where useful performance-wise. It was announced (IIRC) that this would be dealt with for versions 4.8.*, which is out. Haven't checked, though. Doing that now for some random library: % objdump -d libfxt.a | grep cmov | wc -l 749 It struck me only now that the question starting this "what if you have no 'if'?" is (if "if in disguise" is forbidden as well) "then the machine is not a computer". Best, jj * Tom Rokicki <rokicki@gmail.com> [Aug 24. 2013 19:20]:
gcc uses this trick:
solarium:~ rokicki$ cat t.c int mabs(int x) { if (x < 0) return -x ; return x ; } solarium:~ rokicki$ gcc -O5 -S t.c solarium:~ rokicki$ cat t.s ... _mabs: Leh_func_begin1: pushq %rbp Ltmp0: movq %rsp, %rbp Ltmp1: movl %edi, %ecx sarl $31, %ecx addl %ecx, %edi movl %edi, %eax xorl %ecx, %eax popq %rbp ret ... [...]
In case you're not familiar with "Hacker's Delight" by my former colleague Hank Warren, it's a treasure trove of such tricks: http://www.amazon.com/Hackers-Delight-Edition-Henry-Warren/dp/0321842685 Victor On Fri, Aug 23, 2013 at 1:25 PM, Warren D Smith <warren.wds@gmail.com>wrote:
suppose my computer wants |x| but it refuses to perform an "if" statement.
What to do?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
* Victor Miller <victorsmiller@gmail.com> [Aug 26. 2013 07:20]:
In case you're not familiar with "Hacker's Delight" by my former colleague Hank Warren, it's a treasure trove of such tricks:
http://www.amazon.com/Hackers-Delight-Edition-Henry-Warren/dp/0321842685
Recommended. Also http://graphics.stanford.edu/~seander/bithacks.html http://aggregate.org/MAGIC/ http://www.mathematik.uni-bielefeld.de/~sillke/ALGORITHMS/bitmani/ I dare to add http://www.jjj.de/fxt/demo/bits/index.html Of course Knuth's TAOCP, vol.4A is out, a marvel!
Victor
[...]
participants (7)
-
J.P. Grossman -
Joerg Arndt -
Mike Speciner -
Tom Karzes -
Tom Rokicki -
Victor Miller -
Warren D Smith