Convert to inactive sequential if statements

Question

I was stuck there trying to figure out how to convert the last two if statements of the following code to a non-proliferation state.

int u, x, y; x = rand() % 100 - 50; y = rand() % 100 - 50; u = rand() % 4; if ( y > x) u = 5; if (-y > x) u = 4; 

Or, in case the above turns out to be too complicated, you can consider them as:

 if (x > 0) u = 5; if (y > 0) u = 4; 

I think the fact that they don't have an else trap turns me on. If that were the case, I could probably adapt the variation of the abs function (or max / min ) without branching.

The rand() functions you see are not part of the real code. I added them in such a way as to hint at the expected ranges that the variables x , y and u may have at the time of the appearance of the two branches.

An assembly machine code is allowed for this purpose.

EDIT:

After a little brushing, I managed to put together a working idle version:

 int u, x, y; x = rand() % 100 - 50; y = rand() % 100 - 50; u = rand() % 4; u += (4-u)*((unsigned int)(x+y) >> 31); u += (5-u)*((unsigned int)(xy) >> 31); 

Unfortunately, due to the integer arithmetic involved, the original version with if statements is 30% faster.

The compiler knows where the side is.

Answer 1

[Everything: this answer was written with the assumption that the calls to rand () were part of the problem. I suggest an improvement below in this assumption. The OP fears that he only used Rand to tell us the ranges (and presumably distributions) of the x and y values. It is unclear whether it mattered to u. In any case, enjoy my improved answer to a problem that he really had no idea].

I think you'd better rewrite this as:

 int u, x, y; x = rand() % 100 - 50; y = rand() % 100 - 50; if ( y > x) u = 5; else if (-y > x) u = 4; else u = rand() % 4; 

This calls the last rand only 1/4 as often as the OP source code. Since I assume that rand (and division) is much more expensive than comparison and branch, this will be significant savings.

If your rand generator produces a lot of really random bits (e.g. 16) on each call, as you would expect, you can only call it once (I assumed rand is more expensive than divide, YMMV):

 int u, x, y, t; t = rand() ; u = t % 4; t = t >> 2; x = t % 100 - 50; y = ( t / 100 ) %100 - 50; if ( y > x) u = 5; else if (-y > x) u = 4; 

I think the rand function in the MS C library is not good enough for this if you want really random values. I had to code my own; in any case, it turned out to be faster.

You can also get rid of the gap using multiplication by the inverse (untested):

 int u, x, y; unsigned int t; unsigned long t2; t = rand() ; u = t % 4; { // Compute value of x * 2^32 in a long by multiplying. // The (unsigned int) term below should be folded into a single constant at compile time. // The remaining multiply can be done by one machine instruction // (typically 32bits * 32bits --> 64bits) widely found in processors. // The "4" has the same effect as the t = t >> 2 in the previous version t2 = ( t * ((unsigned int)1./(4.*100.)*(1<<32)); } x = (t2>>32)-50; // take the upper word (if compiler won't, do this in assembler) { // compute y from the fractional remainder of the above multiply, // which is sitting in the lower 32 bits of the t2 product y = ( t2 mod (1<<32) ) * (unsigned int)(100.*(1<<32)); } if ( y > x) u = 5; else if (-y > x) u = 4; 

If your compiler will not create the “correct” instructions, just write the assembly code for this.

Answer 2

Some tricks using array indexes can be quite fast if the compiler / processor has one-step instructions for converting the comparison results to values ​​0-1 (for example, x86 "sete", etc.).

 int ycpx[3]; /* ... */ ycpx[0] = 4; ycpx[1] = u; ycpx[2] = 5; u = ycpx[1 - (-y <= x) + (y > x)]; 

Alternative form

 int v1[2]; int v2[2]; /* ... */ v1[0] = u; v1[1] = 5; v2[1] = 4; v2[0] = v1[y > x]; u = v2[-y > x]; 

Almost unreadable ...

NOTE. In both cases, the initialization of array elements containing 4 and 5 can be included in the declaration, and arrays can be static if reentration is not a problem for you.