Which if statement requires less computation?

Question

I have

if (!b && c || a && c)
  //do action a
else 
  //...

Due to some internal relationship between a, b, and c. !b && c || a && c is proved to be equivalent to (! a && b) || c.

I just wonder will (! a && b) || c be simpler than !b && c || a && c? Can you prove it? Assume the chances of a,b,c to be True or False is equal.

I'm not asking which style is better. I'm asking which statement has lower computational complexity. Just like asking quick sort and Bubble Sort, which has lower computational complexity. You will not answer it depends, it is related to compiler and hardware because some hardware have special instruction for Bubble Sort. I hope to hear nlog(n) and n^2.

Answer 1

a good optimizer will make any difference here moot

you can think in how the short circuit works:

with if ((!b && c) || (a && c)) you get

if(b)goto OR2;
if(c)goto then_lbl;
OR2:
if(!a)goto else_lbl;
if(!c)goto else_lbl;
then_lbl://...

while with if((! a && b) || c) (the actual equivalent) you get

if(a) goto OR2;
if(b) goto then_lbl;
OR2:
if(!c) goto else_lbl;
then_lbl://..

so there is no real difference (you always go through 2 or 3 branches)

But I'll repeat my point: this kind of micro optimization is utterly useless to worry about unless it is part of a provable bottleneck and most times the problem isn't a malformed if statement

here you'll find that readability trumps speed

Answer 2

Are you sure it's

(! a && b)

rather than

!(a && b)

?

If not, the brackets are unnecessary and just lead to confusion.

Either way, generally the less operations you have the better for the computer, and in both AND or OR conditions it's better to put the "simplest" first, your most effective way of writing this for the computer (not necessarily the reader) would be:

c || b && ! a

This is assuming C-style operator precedence for the logical operators.

Answer 3

The two statements have the same computational complexity. Both execute in constant time (in complexity terms), which can be written O(1). Since the number of input states is finite (8), it could hardly be otherwise.

If a, b and c are general expressions rather than variable, !b && c || a && c may cause c to be evaluated twice. If c is not idempotent (i.e. if running c a second time doesn't necessarily do what it did the first time), all bets are off. The two expressions you propose also don't execute a, b and c in the same order in all cases, so if their running time depends on the order in which they are called, again, all bets are off.

If what you're wondering is not, in fact, the computational complexity (which deals with asymptotic measures of amounts of computation) but exact the number of computation steps, then the answer is that there is no general answer. The exact number of computation steps depends on which model of computation you choose. For asymptotic analysis, the choice of model is mostly irrelevant: any reasonable model gives the same result (or sometimes there are a few reasonable choices of model, and you need to say which one you're using). If you want a finer analysis, you have to provide a detailed model.

It is completely useless to refine the analysis in this case because the practical difference is going to hinge on a lot of factors that cannot readily be predicted, including:

• what machine code the compiler generates (which depends on the compiler, the compiler version, the optimization settings, the target CPU, and the surrounding code);
• the exact model of CPU (since this will be affected by the amount of prefetching, the branch prediction, the instruction and data pipelines depth, etc.);
• what other code executed before (since this influences the state of the pipelines, the cache, the branch predictor, etc.).

Answer 4

Well cant really answer this because

if (!b && c || a && c)

is not equal to

if ((! a && b) || c)

The truth tables for each are below, abc output:

000 0
001 1
010 0
011 0
100 0
101 1
110 0
111 1

this doesnt match the above

000 0
001 1
010 1
011 1
100 0
101 1
110 0
111 1

test program

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

unsigned int a,b,c;


int main ( void )
{
    for(a=0;a<2;a++)
    for(b=0;b<2;b++)
    for(c=0;c<2;c++)
    {
        printf("%u%u%u ",a,b,c);
        if (!b && c || a && c)
        {
            printf("1\n");
        }
        else
        {
            printf("0\n");
        }
    }

    printf("\n");

    for(a=0;a<2;a++)
    for(b=0;b<2;b++)
    for(c=0;c<2;c++)
    {
        printf("%u%u%u ",a,b,c);
        if ((! a && b) || c)
        {
            printf("1\n");
        }
        else
        {
            printf("0\n");
        }
    }

    return(0);
}

Please add more parenthesis to improve the order of operations, and/or post an equivalent equation, then we can talk about how they differ in complexity.

This is equivalent

    if (c && (!(!a && b)))

note clang's opinion on this syntax:

fun.c:5:12: warning: '&&' within '||' [-Wlogical-op-parentheses]
    if (!b && c || a && c) return(1);
        ~~~^~~~ ~~
fun.c:5:12: note: place parentheses around the '&&' expression to silence this
      warning
    if (!b && c || a && c) return(1);
           ^
        (      )
fun.c:5:22: warning: '&&' within '||' [-Wlogical-op-parentheses]
    if (!b && c || a && c) return(1);
                ~~ ~~^~~~
fun.c:5:22: note: place parentheses around the '&&' expression to silence this
      warning
    if (!b && c || a && c) return(1);
                     ^
                   (     )

Using arm as a test target, the answer is not going to be deterministic BTW, it is compiler and target and system dependent on which is faster, less computation, etc. Looks on the surface with an arm and its instruction set features the first solution with gcc is clean and deterministic (no branches).

This will of course change with each compiler and target and also with whatever code surrounds that if statement. (note the version of gcc and clang/llvm can/will create different results).

unsigned int bool1 ( unsigned int a, unsigned int b, unsigned int c )
{
    if (!b && c || a && c) return(1);
    return(0);
}

unsigned int bool2 ( unsigned int a, unsigned int b, unsigned int c )
{
    if (c && (!(!a && b))) return(1);
    return(0);
}

//gcc

//00000000 <bool1>:
   //0: e2900000    adds    r0, r0, #0
   //4: 13a00001    movne   r0, #1
   //8: e3510000    cmp r1, #0
   //c: 03800001    orreq   r0, r0, #1
  //10: e3520000    cmp r2, #0
  //14: 03a00000    moveq   r0, #0
  //18: 12000001    andne   r0, r0, #1
  //1c: e12fff1e    bx  lr

//00000020 <bool2>:
  //20: e3520000    cmp r2, #0
  //24: 0a000005    beq 40 <bool2+0x20>
  //28: e2711001    rsbs    r1, r1, #1
  //2c: 33a01000    movcc   r1, #0
  //30: e3500000    cmp r0, #0
  //34: 01a00001    moveq   r0, r1
  //38: 13810001    orrne   r0, r1, #1
  //3c: e12fff1e    bx  lr
  //40: e1a00002    mov r0, r2
  //44: e12fff1e    bx  lr

//clang

//bool1:                                  @ @bool1
    //cmp   r1, #0
    //bne   .LBB0_2
    //cmp   r2, #0
    //movne r0, #1
    //movne pc, lr
//.LBB0_2:                                @ %lor.lhs.false
    //cmp   r2, #0
    //movne r2, #1
    //cmp   r0, #0
    //movne r0, #1
    //and   r0, r0, r2
    //mov   pc, lr

//bool2:                                  @ @bool2
    //mov   r3, r0
    //cmp   r2, #0
    //beq   .LBB1_2
    //mov   r0, #1
    //cmp   r3, #0
    //movne pc, lr
    //cmp   r1, #0
    //movne r0, #0
    //b .LBB1_3
//.LBB1_2:                                @ %if.end
    //mov   r0, #0
//.LBB1_3:                                @ %return
    //mov   pc, lr