If x and y both are unsigned integers, and we want to tell whether (x>0 and y>0), then how can we do it? 1. naive method: test x>0 and (if not) then also y>0. 2. x*y>0, but can fail if multiply overflows. 3. The gnu superoptimizer found 44 nonobvious methods, each involving 4 instructions, at least one of which always is subtract-with-borrow and/or add-with-carry. I think the basic idea is: if you regard (x,y) as a 2-digit number, and subtract (1,1), then you will generate at least one borrow if and only if (x=0 or y=0). 4. ((-x)&(-y))>>31 should be nonzero if x>0 and y>0, provided neither x nor y was greater than 2^31 - 1. On a 32-bit machine. -- Warren D. Smith
get x OR y and test if negative. On 16 Apr 2014, at 21:45, Warren D Smith wrote:
If x and y both are unsigned integers, and we want to tell whether (x>0 and y>0), then how can we do it?
1. naive method: test x>0 and (if not) then also y>0.
2. x*y>0, but can fail if multiply overflows.
3. The gnu superoptimizer found 44 nonobvious methods, each involving 4 instructions, at least one of which always is subtract-with-borrow and/or add-with-carry. I think the basic idea is: if you regard (x,y) as a 2-digit number, and subtract (1,1), then you will generate at least one borrow if and only if (x=0 or y=0).
4. ((-x)&(-y))>>31 should be nonzero if x>0 and y>0, provided neither x nor y was greater than 2^31 - 1. On a 32-bit machine.
-- Warren D. Smith
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The meaning and purpose of life is to give life purpose and meaning. The instigation of violence indicates a lack of spirituality.
The test is > 0, not >= 0. OR-ing them together fails if, say, x=0 and y=1. They are not both > 0, so the answer should be false. Tom David Makin writes:
get x OR y and test if negative.
On 16 Apr 2014, at 21:45, Warren D Smith wrote:
If x and y both are unsigned integers, and we want to tell whether (x>0 and y>0), then how can we do it?
1. naive method: test x>0 and (if not) then also y>0.
2. x*y>0, but can fail if multiply overflows.
3. The gnu superoptimizer found 44 nonobvious methods, each involving 4 instructions, at least one of which always is subtract-with-borrow and/or add-with-carry. I think the basic idea is: if you regard (x,y) as a 2-digit number, and subtract (1,1), then you will generate at least one borrow if and only if (x=0 or y=0).
4. ((-x)&(-y))>>31 should be nonzero if x>0 and y>0, provided neither x nor y was greater than 2^31 - 1. On a 32-bit machine.
-- Warren D. Smith
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The meaning and purpose of life is to give life purpose and meaning. The instigation of violence indicates a lack of spirituality.
"WDS" == Warren D Smith <warren.wds@gmail.com> writes:
WDS> If x and y both are unsigned integers, and we want to tell whether WDS> (x>0 and y>0), WDS> then how can we do it? In a language with a logical AND, x AND y is true iff both are > 0. In amd64 assembly, this seems best: xor %eax,%eax test %rsi,%rdi setne %al retq In arm assembly, that looks like: tst r0, r1 moveq r0, #0 movne r0, #1 bx lr -JimC -- James Cloos <cloos@jhcloos.com> OpenPGP: 1024D/ED7DAEA6
On 4/17/14, James Cloos <cloos@jhcloos.com> wrote:
WDS> If x and y both are unsigned integers, and we want to tell whether WDS> (x>0 and y>0), WDS> then how can we do it?
In a language with a logical AND,
x AND y is true iff both are > 0.
--at least with C's meaning of AND, 1 AND 2 = 0, a counterexample.
1 and 2 giving zero is bitwise and not logical.... Also you could just calculate x plus y and both are >0 if either zero bit is not set or if carry bit is set. On 17 Apr 2014, at 17:55, Warren D Smith wrote:
On 4/17/14, James Cloos <cloos@jhcloos.com> wrote:
WDS> If x and y both are unsigned integers, and we want to tell whether WDS> (x>0 and y>0), WDS> then how can we do it?
In a language with a logical AND,
x AND y is true iff both are > 0.
--at least with C's meaning of AND, 1 AND 2 = 0, a counterexample.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The meaning and purpose of life is to give life purpose and meaning. The instigation of violence indicates a lack of spirituality.
Sorry - I should have stuck to my comment about logical vs. bitwise ;) On 17 Apr 2014, at 18:23, David Makin wrote:
1 and 2 giving zero is bitwise and not logical....
Also you could just calculate x plus y and both are >0 if either zero bit is not set or if carry bit is set.
On 17 Apr 2014, at 17:55, Warren D Smith wrote:
On 4/17/14, James Cloos <cloos@jhcloos.com> wrote:
WDS> If x and y both are unsigned integers, and we want to tell whether WDS> (x>0 and y>0), WDS> then how can we do it?
In a language with a logical AND,
x AND y is true iff both are > 0.
--at least with C's meaning of AND, 1 AND 2 = 0, a counterexample.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The meaning and purpose of life is to give life purpose and meaning. The instigation of violence indicates a lack of spirituality.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The meaning and purpose of life is to give life purpose and meaning. The instigation of violence indicates a lack of spirituality.
[net is down here right now; this may take a while to get out... -JimC]
"WS" == Warren D Smith <warren.wds@gmail.com> writes:
x AND y is true iff both are > 0.
WS> --at least with C's meaning of AND, WS> 1 AND 2 = 0, Try this: #include <stdio.h> #include <stdlib.h> int main (int c, char *v[]) { unsigned long x, y, lz, bz; if (c < 3) { fprintf (stderr, "Useage: %s <int> <int>\n", v[0]); return -1; } x = strtol (v[1], NULL, 0); y = strtol (v[2], NULL, 0); bz = x & y; lz = x && y; printf ("%lu & %lu = %lu (%s)\n%lu && %lu = %lu (%s)\n", x, y, bz, bz ? "true" : "false", x, y, lz, lz ? "true" : "false"); } -JimC -- James Cloos <cloos@jhcloos.com> OpenPGP: 1024D/ED7DAEA6
In C/C++ (and Java?) James logical "and" would be: if ((x) && (y)) though maybe if (x && y) would work too. On 17 Apr 2014, at 16:52, James Cloos wrote:
"WDS" == Warren D Smith <warren.wds@gmail.com> writes:
WDS> If x and y both are unsigned integers, and we want to tell whether WDS> (x>0 and y>0), WDS> then how can we do it?
In a language with a logical AND,
x AND y is true iff both are > 0.
In amd64 assembly, this seems best:
xor %eax,%eax test %rsi,%rdi setne %al retq
In arm assembly, that looks like:
tst r0, r1 moveq r0, #0 movne r0, #1 bx lr
-JimC -- James Cloos <cloos@jhcloos.com> OpenPGP: 1024D/ED7DAEA6
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The meaning and purpose of life is to give life purpose and meaning. The instigation of violence indicates a lack of spirituality.
Seems like people are choosing to ignore various words in the question. Words such as "unsigned". But of course, this is a somewhat ill-defined question. Are you asking for a given programming language? A given machine language? What do you want the result of the test to be? A boolean? 0 or 1? Something zero or nonzero? Your numbered points make it even less clear. For example, on a pdp-11, multiplying (MUL) does indeed work, as it sets the Z flag based on the full result, whether or not it overflows a single word. (It treats the operands as signed, but that doesn't matter in this case.) In python, x and y does what you might want, since the semantics are to return x if x evaluates false and otherwise return y. (Various objects evaluate false, such as: False, 0, and empty strings and lists.) Of course, internally lots of machine instructions get executed to make this happen. Another idea is 0/x/y which will raise a divide-by-zero exception unless x and y are both nonzero. --ms On 2014-04-16 16:45, Warren D Smith wrote:
If x and y both are unsigned integers, and we want to tell whether (x>0 and y>0), then how can we do it?
1. naive method: test x>0 and (if not) then also y>0.
2. x*y>0, but can fail if multiply overflows.
3. The gnu superoptimizer found 44 nonobvious methods, each involving 4 instructions, at least one of which always is subtract-with-borrow and/or add-with-carry. I think the basic idea is: if you regard (x,y) as a 2-digit number, and subtract (1,1), then you will generate at least one borrow if and only if (x=0 or y=0).
4. ((-x)&(-y))>>31 should be nonzero if x>0 and y>0, provided neither x nor y was greater than 2^31 - 1. On a 32-bit machine.
Yet another way, if only arithmetic right shift (>>) worked "properly": (-2>>x)&(-2>>y)&1 On 2014-04-17 15:10, Mike Speciner wrote:
Seems like people are choosing to ignore various words in the question. Words such as "unsigned". But of course, this is a somewhat ill-defined question. Are you asking for a given programming language? A given machine language? What do you want the result of the test to be? A boolean? 0 or 1? Something zero or nonzero? Your numbered points make it even less clear.
For example, on a pdp-11, multiplying (MUL) does indeed work, as it sets the Z flag based on the full result, whether or not it overflows a single word. (It treats the operands as signed, but that doesn't matter in this case.)
In python, x and y does what you might want, since the semantics are to return x if x evaluates false and otherwise return y. (Various objects evaluate false, such as: False, 0, and empty strings and lists.) Of course, internally lots of machine instructions get executed to make this happen.
Another idea is 0/x/y which will raise a divide-by-zero exception unless x and y are both nonzero.
--ms
On 2014-04-16 16:45, Warren D Smith wrote:
If x and y both are unsigned integers, and we want to tell whether (x>0 and y>0), then how can we do it?
1. naive method: test x>0 and (if not) then also y>0.
2. x*y>0, but can fail if multiply overflows.
3. The gnu superoptimizer found 44 nonobvious methods, each involving 4 instructions, at least one of which always is subtract-with-borrow and/or add-with-carry. I think the basic idea is: if you regard (x,y) as a 2-digit number, and subtract (1,1), then you will generate at least one borrow if and only if (x=0 or y=0).
4. ((-x)&(-y))>>31 should be nonzero if x>0 and y>0, provided neither x nor y was greater than 2^31 - 1. On a 32-bit machine.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
atan2(y,x)/pi<1/2 Don't laugh too hard; as floating point and GPU's become ubiquitous, this approach may actually be as fast as some other approaches -- particularly in very deeply pipelined units. Of course, it would work somewhat more reliably if atan2(y,x)/pi were the primitive instead of atan2(y,x) itself.
Aha - finally, using bitwise or and and: Signed result of [(-x or x) and (-y or y)] is negative it both x and y are non-zero (similar to method 4 below but for whole range any CPU integer bitwidth) On 16 Apr 2014, at 21:45, Warren D Smith wrote:
If x and y both are unsigned integers, and we want to tell whether (x>0 and y>0), then how can we do it?
1. naive method: test x>0 and (if not) then also y>0.
2. x*y>0, but can fail if multiply overflows.
3. The gnu superoptimizer found 44 nonobvious methods, each involving 4 instructions, at least one of which always is subtract-with-borrow and/or add-with-carry. I think the basic idea is: if you regard (x,y) as a 2-digit number, and subtract (1,1), then you will generate at least one borrow if and only if (x=0 or y=0).
4. ((-x)&(-y))>>31 should be nonzero if x>0 and y>0, provided neither x nor y was greater than 2^31 - 1. On a 32-bit machine.
-- Warren D. Smith
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The meaning and purpose of life is to give life purpose and meaning. The instigation of violence indicates a lack of spirituality.
participants (6)
-
David Makin -
Henry Baker -
James Cloos -
Mike Speciner -
Tom Karzes -
Warren D Smith