Can you simplify this algorithm?

Question

One for the mathematicians. This has gone around the office and we want to see who can come up with a better optimised version.

(((a+p) <= b) && (a == 0 || a > 1) && (b >= p)) && 
    ((b - (a + p) == 0) || (b - (a + p) > 1))

Edit: all data is positive int's

Edit: Better == refactored for simplicity

Answer 1

I wouldnt do all math in that expression. Such as b - ( a + p ) is evaluated twice. If possible, split them into variables instead.

Also, writing a polish notiation tree might help you optimize it, everything that you see twice, can be re-used.

Answer 2

Since the ints are unsigned, (a==0 || a>1) can be substituted for (a !=1).

With a first pass, you can reduce it to this:

uint sum = a + p;
return ((sum <= b) && (a != 1) && (b >= p)) && (b - sum != 1);

Also, it would be much more readable if you were able to give more meaningful names to the variables. For instance, if a and p were pressures, then a+p could be substitued as PressureSum.

Answer 3

Refactor for simplicity by introducing more local variables which indicate the meaning of each expression. This is hard for us to do with no idea of what a, b and p mean.

Answer 4

Well

((b - (a + p) == 0) || (b - (a + p) > 1))

Would be better writen as:
(b - (a + p) >= 0)  

Applying this to the whole string you get:

((a+p) <= b) && (a > 1) && (b >= p)) && (b - (a + p) >= 0) 


(a + p) <= b is the same thing as b - (a + p) >= 0

So you can get rid of that leaving:

((a+p) <= b) && (a > 1) && (b >= p))

Answer 5

First iteration:

bool bool1 = ((a+p) <= b) && (a == 0 || a > 1) && (b >= p);
bool bool2 = (b - (a + p) == 0) || (b - (a + p) > 1);

return bool1 && bool2;

Second iteration:

int value1 = b - (a + p);
bool bool1 = (value1 >= 0) && (a == 0 || a > 1) && (b >= p);
bool bool2 = (value1 == 0) || (value1 > 1);

return bool1 && bool2;

Third iteration (all positives)

int value1 = b - (a + p);
bool bool1 = (value1 >= 0) && (a != 1) && (b >= p);
bool bool2 = (value1 == 0) || (value1 > 1);

return bool1 && bool2;

4th iteration (all positives)

int value2 = b - p;
int value1 = value2 - a;
bool bool1 = (value1 >= 0) && (a != 1) && (b - p >= 0);
bool bool2 = (value1 == 0) || (value1 > 1);

return bool1 && bool2;

5th iteration:

int value2 = b - p;
int value1 = value2 - a;
bool bool1 = (value1 >= 0) && (a != 1) && (value2 >= 0);
bool bool2 = (value1 == 0) || (value1 > 1);

return bool1 && bool2;

Answer 6

b >= p && b != p+1

EDIT: Ok, that didn't work, but this one does:

a != 1 && b >= a+p && b-a-p != 1

Answer 7

I think PEZ has it right.

Answer 8

Since they are all positive ints a lot of the repetition can be removed:

So as a first step,

(((a+p) <= b) && (a == 0 || a > 1) && (b >= p)) && ((b - (a + p) == 0) || (b - (a + p) > 1))

becomes

((a+p) <= b) && (a != 1) && (b >= p)) && ((b - (a + p) != 1)

For clarity, this is just replacing the (foo == 0 || foo > 1) pattern with foo != 1

That pattern appears twice above, once with foo = a, and once with foo = (b - (a+p))

Answer 9

If the formula works and come from your business rules there is no real need to simplify it. The compiler probably knows better than us how to optimizing the formula.

The only thing you should do is use better variables names which reflect the business logic.

Beware of applying any of the proposed solution before unit testing them.

Answer 10

bap = b - (a + p)
bap >= 0 && bap != 1 && a != 1

EDIT: Now I've got -2 for an honest attempt at helping out and also for what seems to me to be a valid answer. For you who can use Python, here are two functions, one with the question and one with my answer:

def question(a, b, p):
    return (((a+p) <= b) and (a == 0 or a > 1) and (b >= p)) or ((b - (a + p) == 0) or (b - (a + p) > 1))

def answer(a, b, p):
    bap = b - (a + p)
    return bap >= 0 and bap != 1 and a != 1

Answer 11

(a + p <= b) && (a != 1) && (b - a - p != 1);

Answer 12

s = a + p
b >= s && a != 1 && b - s - 1 > 0

Checked, returns the same boolean value as the question.

Program that I have used to check: (had fun writing it)

#include <iostream>
using namespace std;

typedef unsigned int uint;

bool condition(uint a, uint b, uint p)
{
     uint s = a + p;
     return uint(    b >= s && a != 1 && b - s - 1 > 0    )
     == uint(    (((a+p) <= b) && (a == 0 || a > 1) && (b >= p))
                 && ((b - (a + p) == 0) || (b - (a + p) > 1))    );
}

void main()
{
    uint i = 0;
    uint j = 0;
    uint k = 0;

    const uint max = 50;

    for (uint i = 0; i <= max; ++i)
        for (uint j = 0; j <= max; ++j)
            for (uint k = 0; k <= max; ++k)
                if (condition(i, j, k) == false)
                {
                    cout << "Fails on a = " << i << ", b = " << j;
                    cout << ", p = " << k << endl;

                    int wait = 0;
                    cin >> wait;
                }
}

Answer 13

Alright, I'm hoping that I did my math right here, but if I'm right, then this simplifies quite a bit. Granted it doesn't look the same in the end, but the core logic should be the same.

// Initial equation
(((a + p) <= b) && (a == 0 || a > 1) && (b >= p)) && ((b - (a + p) == 0) || (b - (a + p) > 1))

// ((a + p) <= b) iif a = 0 && p = b; therefore, b = p and a = 0 for this to work
(b == p) && ((b - (a + p) == 0) || (b - (a + p) > 1))

// Simplification, assuming that b = p and a = 0
(b == p) && (a == 0)

However, if we are operating under the assumption that zero is neither positive or negative then that implies that any value for a provided to the equation is going to be greater than or equal to one. This in turn means that the equation will always evaluate to false due to the fact that the following:

(a == 0 || a > 1)

Would only evaluate to true when a >= 2; however, if the following is also true:

(b >= p)

Then that means that p is at least equal to b, thus:

((a + p) <= b)

By substitution becomes:

((2 + b) <= b)

Which can clearly never evaluate to true.

Answer 14

(a!=1) && ((b==a+p) || (b>1+a+p))

It may not the simplest, but should be the one of most readable.

Answer 15

This is as simple as I could get it.

def calc(a, b, p):
    if (a != 1):
        temp = a - b + p
        if temp == 0 or temp < -1:
            return True
    return False

It could also be written as:

def calc(a, b, p):
    temp = a - b + p
    return a != 1 and (temp == 0 or temp < -1)

Or as:

def calc(a, b, p):
    temp = a - b + p
    return a != 1 and temp <= 0 and temp != -1

Answer 16

I added this as a comment to nickf's answer but thought I'd offer it up as an answer on it's own. The good answers all seem to be a variation of his, including mine. But since we're not depending on the compiler for optimization (if the OP were, we wouldn't even be doing this) then boiling this down from 3 ANDs to the following means that there will be values where only 2 of the 3 portions will need to be evaluated. And if this is being done in a script, it would make a difference as opposed to compiled code.

(a != 1) && ((b > (a + p + 1)) || (b == (a + p))))

Based on a comment, I'm going to add this wrt this being better than the AND version:

I guess it depends on whether your true results data set is larger than 50 percent of the input sets. The more often the input is true, the better my variation will be. So, with this equation, it looks like the AND style will be better (at least for my input data set of 0-500).

Answer 17

Tested with a,b,p from 0 to 10000:

a != 1 && a != (b-p-1) && a <= (b-p);

I think it can be simplified even more.

Answer 18

If a, b and p are positive integers (assuming that the positive range include the 0 value) then the expression (((a+p) <= b) && (a == 0 || a > 1) && (b >= p)) && ((b - (a + p) == 0) || (b - (a + p) > 1)) can be reduced to ((a+p)<=b) && (a!=1) && ((b-(a+p))!=1)

Let me demonstrate it: In the first part of the expression there is a condition, ((a+p)<=b), that if valuated true render true the second part: ((b - (a + p) == 0) || (b - (a + p) > 1)). If it is true that (b >=(a+p)) then (b - (a+p)) have to be greater or equal to 0, we need to assure that (b-(a+p))!=1. Put this term aside for awhile and go on.

Now we can concentrate our efforts on the the first part (((a+p) <= b) && (a == 0 || a > 1) && (b >= p)) && ((b-(a+p))!=1)

If a is positive then it is always >=0 and so we can drop the test (a == 0 || a > 1) if favor of (a!=1) and reduce first part of the expression to (((a+p) <= b) && (b >= p) && (a!=1)).

For the next step of the reduction you can consider that if b >= (a+p) then, obviously b>=p (a is positive) and the expression can be reduced to

((a+p)<=b) && (a!=1) && ((b-(a+p))!=1)

Answer 19

b >= (a+p) && a>=1

even b>=p is redundant as this will always be the case for a>=1

Answer 20

(((a+p) <= b) && (a == 0 || a > 1) && (b >= p)) && ((b - (a + p) == 0) || (b - (a + p) > 1))

since a >=0 (positive integers), the term (a == 0 || a > 1) is always true

if ((a+p) <= b) then (b >= p) is true when a,b,p are >=0

therefore ((a+p) <= b) && (a == 0 || a > 1) && (b >= p)) && ((b - (a + p) == 0) reduces to

b>=(a+p)

(b - (a + p) == 0) || (b - (a + p) > 1) is equivalent to b>=(a+p)

therefore the whole equation reduces to

**b>= (a+p)**

Answer 21

my apologies for the mistake in the original derivation. This is what happens when you don't bother to unit test after refactoring!

the corrected derivation follows, in the form of a test program.

The short answer is:

((a > 1) && (skeet == 0)) || ((a > 1) && (jon > 0) && (skeet < -1));

where

jon = (b - p)
skeet = (a - jon);

---

class Program
{
    static void Main(string[] args)
    {
        bool ok = true;
        for (int a = 1; a < 100; a++)
        {
            Console.Write(a.ToString());
            Console.Write("...");

            for (int b = 1; b < 100; b++)
            {
                for (int p = 1; p < 100; p++)
                {
                    bool[] results = testFunctions(a, b, p);
                    if (!allSame(results))
                    {
                        Console.WriteLine(string.Format(
                            "Fails for {0},{1},{2}", a, b, p));
                        for (int i = 1; i <= results.Length; i++)
                        {
                            Console.WriteLine(i.ToString() + ": " + 
                                results[i-1].ToString());
                        }

                        ok = false;
                        break;
                    }
                }
                if (!ok) { break; }
            }
            if (!ok) { break; }
        }
        if (ok) { Console.WriteLine("Success"); }
        else { Console.WriteLine("Failed!"); }
        Console.ReadKey();
    }

    public static bool allSame(bool[] vals)
    {
        bool firstValue = vals[0];
        for (int i = 1; i < vals.Length; i++)
        {
            if (vals[i] != firstValue)
            {
                return false;
            }
        }
        return true;
    }

    public static bool[] testFunctions(int a, int b, int p)
    {
        bool [] results = new bool[16];

        //given: all values are positive integers
        if (a<=0 || b<=0 || p<=0)
        {
            throw new Exception("All inputs must be positive integers!");
        }

        //[1] original expression
        results[0] = (((a+p) <= b) && (a == 0 || a > 1) && (b >= p)) && 
            ((b - (a + p) == 0) || (b - (a + p) > 1));

        //[2] a==0 cannot be true since a is a positive integer
        results[1] = (((a+p) <= b) && (a > 1) && (b >= p)) && 
            ((b - (a + p) == 0) || (b - (a + p) > 1));

        //[3] rewrite (b >= p) && ((a+p) <= b) 
        results[2] = (b >= p) && (b >= (a+p)) && (a > 1) && 
            ((b - (a + p) == 0) || (b - (a + p) > 1));

        //[4] since a is positive, (b>=p) guarantees (b>=(p+a)) so we 
        //can drop the latter term
        results[3] = (b >= p) && (a > 1) && 
            ((b - (a + p) == 0) || (b - (a + p) > 1));

        //[5] separate the two cases b>=p and b=p
        results[4] = ((b==p) && (a > 1) && ((b - (a + p) == 0) || 
            (b - (a + p) > 1))) || ((b > p) && (a > 1) && 
            ((b - (a + p) == 0) || (b - (a + p) > 1)));

        //[6] rewrite the first case to eliminate p (since b=p 
        //in that case)
        results[5] = ((b==p) && (a > 1) && ((-a == 0) || 
            (-a > 1))) || ((b > p) && (a > 1) && 
            (((b - a - p) == 0) || ((b - a - p) > 1)));

        //[7] since a>0, neither (-a=0) nor (-a>1) can be true, 
        //so the case when b=p is always false
        results[6] = (b > p) && (a > 1) && (((b - a - p) == 0) || 
            ((b - a - p) > 1));

        //[8] rewrite (b>p) as ((b-p)>0) and reorder the subtractions
        results[7] = ((b - p) > 0) && (a > 1) && (((b - p - a) == 0) || 
            ((b - p - a) > 1));

        //[9] define (b - p) as N temporarily
        int N = (b - p);
        results[8] = (N > 0) && (a > 1) && (((N - a) == 0) || ((N - a) > 1));

        //[10] rewrite the disjunction to isolate a
        results[9] = (N > 0) && (a > 1) && ((a == N) || (a < (N - 1)));

        //[11] expand the disjunction
        results[10] = ((N > 0) && (a > 1) && (a == N)) ||
            ((N > 0) && (a > 1) && (a < (N - 1)));

        //[12] since (a = N) in the first subexpression we can simplify to
        results[11] = ((a == N) && (a > 1)) || 
            ((N > 0) && (a > 1) && (a < (N - 1)));

        //[13] extract common term (a > 1) and replace N with (b - p)
        results[12] = (a > 1) && ((a == (b - p)) || 
            (((b - p) > 0) && (a < (b - p - 1))));

        //[14] extract common term (a > 1) and replace N with (b - p)
        results[13] = (a > 1) && (((a - b + p) == 0) || 
            (((b - p) > 0) && ((a - b + p) < -1)));

        //[15] replace redundant subterms with intermediate 
        //variables (to make Jon Skeet happy)
        int jon = (b - p);
        int skeet = (a - jon);   //(a - b + p) = (a - (b - p))
        results[14] = (a > 1) && ((skeet == 0) || 
            ((jon > 0) && (skeet < -1)));

        //[16] rewrite in disjunctive normal form
        results[15] = ((a > 1) && (skeet == 0)) || 
            ((a > 1) && (jon > 0) && (skeet < -1));

        return results;
    }
}

Answer 22

Hi All, how is about the following logic, please comment it:

((a == 0 || a > 1) && ((b-p) > 1) )

Answer 23

(((a+p) <= b) && (a == 0 || a > 1) && (b >= p)) && ((b - (a + p) == 0) || (b - (a + p) > 1))

1) (a == 0 || a > 1) is (a != 1)

2) (b >= p) is (b - p >= 0)

(a + p <= b) is (b - p >= a), which is stronger than (b - p >= 0).

First condition reduced to (a != 1) && (b - p >= a).

3) (b - (a + p) == 0) is (b - a - p == 0) is (b - p == a).

(b - (a + p) > 1) is (b - a - p > 1) is (b - p > 1 + a).

Since we had (b - p >= a) and we're using && operation, we may say that (b - p >= a) covers (b - p == a && b - p > 1 + a).

Hence, the whole condition will be reduced to

(a != 1 && (b - p >= a))

There's a tempation to reduce it further to (b >= p), but this reduction won't cover prohibition of b = p + 1, therefore (a != 1 && (b - p >= a)) is the condition.

Answer 24

// In one line:
return (a != 1) && ((b-a-p == 0) || (b-a-p > 1))

// Expanded for the compiler:
if(a == 1)
    return false;

int bap = b - a - p;

return (bap == 0) || (bap > 1);

If you post the processor you are using, I can optimize for assembly. =]

Answer 25

This question has been pretty comfortably answered already in practice, but there is one point I mention below which I have not seen anyone else raise yet.

Since we were told to assume a >= 0, and the first condition assures that b - (a + p) >= 0, the bracketed || tests can be turned into tests against inequality with 1:

(a + p <= b) && (a != 1) && (b >= p) && (b - a - p != 1)

It is tempting to remove the check (b >= p), which would give nickf's expression. And this is almost certainly the correct practical solution. Unfortunately, we need to know more about the problem domain before being able to say if it is safe to do that.

For instance, if using C and 32-bit unsigned ints for the types of a, b, and p, consider the case where a = 2^31 + 7, p = 2^31 + 5, b = 13. We have a > 0, (a + p) = 12 < b, but b < p. (I'm using '^' to indicate exponentiation, not C bitwise xor.)

Probably your values will not approach the kind of ranges where this sort of overflow is an issue, but you should check this assumption. And if it turns out to be a possibility, add a comment with that expression explaining this so that some zealous future optimiser does not carelessly remove the (b >= p) test.

Answer 26

jjngy up here has it right. Here's a proof that his simplified formula is equivalent to the original using the Coq Proof Assistant.

Require Import Arith.
Require Import Omega.

Lemma eq : forall (a b p:nat),
(((a+p) <= b) /\ ((a = 0) \/ (a > 1)) /\ (b >= p)) /\ 
    ((b - (a + p) = 0) \/ (b - (a + p) > 1)) <-> 
((a + p <= b) /\ ~ (a= 1) /\ ~ (b - a - p = 1)).
Proof. intros; omega. Qed.

Answer 27

I feel (a != 1) && (a + p <= b) && (a + p != b - 1) is slightly more clear. Another option is:

int t = b-p; (a != 1 && a <= t && a != t-1)

Basically a is either 0, t, or lies between 2 and t-2 inclusive.