Can you simplify this expression?

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 == simpler

Sweetbread

Are there any constraints on the variables? E.g. integer type, implicit int->bool conversion, etc? – Palaeolithic

What types are those variables? int? float? – Bookkeeping

That is not an algorithm. It is a function. – Triglyph

And could you please give a hint on your definition of "better"? – Palaeolithic

I'd say they are probably non-negative, because otherwise the "a==0" could be left out entirely. – Bookkeeping

You're probably responsible for hundreds of lost work hours now, Adam. =) – Burck

Well glad your all helping! I'll run some of these through and post my results. – Sweetbread

What's the language? Rules of precedence are not necessarily the same in all languages. – Monoacid

So you are going to post what the answer that your office came up with is, right? – Belia

@Adam: So you mean they're all positive ints, not just "non-negative" ( >= 0) ints? – Uria

Once im back in the office i'll find out which one got picked... – Sweetbread

Just wanted to plug: codegolf.stackexchange.com I suspect the question is even more suited there :) – Pungy

Answer 1

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

Uria

Passes my test (All possible combination of 0-200) – Triglyph

how do you get from (b >= p)) && ((b - (a + p) != 1) to (b - a - p != 1) ...I can see that the last terms are equivalent, but how do you remove the b>=p? – Tiemannite

a+p<=b implies b>=p. a+p<=b => b>=p+a – Substrate

hmm...i see how a+b <= b is equivalent to b>=a+p but it took me a while to see how that implies b>=p...together with the fact a>=0 yes I see your point. – Tiemannite

If you use a script instead of relying on a compiler, you could speed it up by 1st & 3rd portions into an OR... (a != 1) && ((b > (a+p+1)) || (b == (a+p)))) – Rhythmics

@[Brian Genisio]: did you try the combinations with some value near or equal to MAX_INT? – Helli

Actually, if we're talking about optimising here, then my variation with the OR in it and the reordering is probably even better. – Rhythmics

fyi. just added my variation as a standalone answer. – Rhythmics

I think you're still unnecessarily doing an a+p operation here, since (b-a-p) = (b-(a+p)), and you already calculated (a+p) – Irrelative

@[Andrea Francia] No, only 0-200. Some Max tests would be really useful, assuming the input range can approach Max. – Triglyph

@Triptych, i don't think that creating a new variable to save yourself one subtraction is optimal at all. Plus, that makes it no longer a one-liner. – Uria

After failing to reduce this further (and deleting my failed answer) I have to agree that this solution is optimal. +1 – Helpmate

Further simplification (probably something the compiler would do, but j.i.c.): define: z = a + p (b >= z) && (b != z + 1) && (a != 1) – Planogamete

(a != 1) is simplest to evaluate and can be done first. @Brian's suggestion works for all combinations [0,600). – Centralia

a + p <= b implies 0 <= b - a - p, and given all ints >=0, wouldn't the this clause be redundant with b-a-p != 1? – Colum

@Calyth, I just tested : (a + p <= b) && (a != 1) does not match the OP's solution. – Centralia

@strager, you removed the wrong clause, Calyth meant (a != 1) && (b - a - p != 1), but that makes little difference... because @Calyth, yes, that's equivalent, but it can't be removed. (b - a - p < 0) can easily be true if all are positive ints. E.g. a=2, b=7, p=3 – Sucrase

@mercator, Woops, I copied the wrong thing. Well, I tested what he meant, and it was wrong (as you said). – Centralia

please show your work, and explain a!=1 instead of a>1 given that a is a positive integer ;-) – Overspread

The question is a bit unclear about it. But since the original expression contains the test for a == 0 we have sort to assume that positive integers here include 0. Think of it as +0. – Burck

@PEZ: 0 is not a positive integer. But if we assume positive integers, then a!=1 is just as good as a>1 ;-) – Overspread

I'd write the third term (b - a - p != 1) as (a + p != b - 1) for symmetry with the first term and then reorganize the terms like this: (a + p <= b) && (a + p != b - 1) && (a != 1) – Contemplate

Answer 2

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.

Helli

I agree with that. Especially if the formula came from some sort of scientific paper. You want those types of formulas to read verbatim, so you can cite the source. – Triglyph

Huh. "Do not use brain"? Simplifying overcomplicated conditionals is not 'optimization', it is refactoring / improving clarity. – Frentz

What if it isn't compiled? It could be in a script that doesn't optimize. – Rhythmics

@Planogamete - Good point on the sources, but scientific papers usually give the simplest form of an equation in the paper. Generally, those formulas tend to get a bit longer when you code them up. – Belia

Absolutely. It's not overcomplicated if the business rule itself is reflected meaningfully in the current configuration (which would be obvious with better variable names...) – Pretentious

I can't believe I'm saying this, but I think in this particular kind of scenerio it is not true to say that "the compiler probably knows better than us how to optimize the formula." Some of the deductions can be very complex. (continued) – Shafer

Your other points I agree with completely, and would probably not alter the formula. – Shafer

i have encountered business rules like this in real programs, and they invariably result from 'tweaking' over the years, but with no one simplifying the math to realize that terms cancel. In one case a very long, multivariate complex boolean condition reduced to a simple two-variable disjunction! – Overspread

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.

Formaldehyde

I'm reading Uncle Bob's Clean Code atm and this code could have been one of the before pictures for refactoring methods. – Reeba

Great answer. Build functions with good names--yours is the right answer. – Bigg

changing the names of a, b, and p does not remove the need to simplify this unnecessarily complex conditional expression; adding intermediate variables would, in fact, make the simplifacation more difficult. – Overspread

I strongly suspect that adding intermediate variables would make it simpler to understand - which helps it to be simplified afterwards. Note that I didn't just recommend changing the names of the variables - extract common expressions and give them a meaningful name. – Formaldehyde

but extracting common expressions and encapsulating them behind another name removes the ability to eliminate subexpressions... – Overspread

redid my answer to incorporate your advice ;-) – Overspread

The key word you forgot was "meaningful" :) – Formaldehyde

yeah but since i don't know the context of the original rule i used the two words that carry the most meaning on SO ;-) – Overspread

Downvoters: please leave a comment when you downvote, otherwise it has little positive impact. – Formaldehyde

Answer 4

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

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

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

Anisaanise

How did you get rid of the "(a == 0 || a > 1)" part? – Burck

@TomWij: yeah, it turns out a isn't so irrelevant after all =)) – Eloign

Answer 5

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

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

Whistler

i think all answers should have a proof going through Tom Wizmap's test. – Garlinda

Answer 6

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.

Borowski

Answer 7

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))

Tiemannite

how? both should be false because they have the same b>=p condition, which is false, and makes the major && condition false. – Tiemannite

@TomWij: a and b cannot be = 0, they are both positive integers (which means > 0) – Overspread

since the original code includes "a == 0", then I think it's safe to assume he meant "non-negative integers", not "positive integers" – Uria

Answer 8

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;
                }
}

Flanigan

Using your test fixture, I do not get a failure on my solution, though you commented that It failed on 0,2,1 – Triglyph

Clearer than "b - s - 1 > 0" that is. – Burck

What about 2,4,2: 4-(2+2)-1 = -1. Do you rely on overflow here? Nifty, but what if range checking is done? (By the way, this is why b-s>1 will not work,as 4-(2+2)=0 is valid by (b - (a + p) == 0).) – Prae

Uh, people down vote too easily to my opinion. There is nothing wrong with my answer... – Flanigan

doesn't casting to unit eliminate negative results? and thus possibly hide errors? – Overspread

3 satisfiability problem ? (3SAT) – Garlinda

Answer 9

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.

Triglyph

No, it does not fail. I just tested it. Both implementations return false on Function(0, 2, 1). Please retract that comment. – Triglyph

@TomWij: a cannot be = 0, it is a positive integer (which means > 0) – Overspread

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

Burck

Fails on a = 0, b = 0, p = 1; fill in your equatation and in the question, it won't give the same boolean value. – Flanigan

this will only work if bap is a signed integer. otherwise bap will rollover to UINT_MAX. – Eloign

For me it returns False in both cases. – Burck

yep i've just tested this on all combinations of 0-199 which is 8 million tests (overkill i know), and it works. – Uria

Answer 11

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

Furious

Answer 12

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.

Congo

Answer 13

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;
    }
}

Overspread

@Steven: (a == 0 || a > 1) cannot be reduced to (a > 1). It's (a != 1). – Ape

@Ape - If we are assuming that 0 is neither negative or positive then (a > 1) and (a != 1) have the same truth table. – Belia

You say both "(a == 0 || a > 1) reduces to (a > 1)" and "N == 0 || N > 1 implies N >= 0 for positive integers", but neither is correct. Assuming a >=0 (as we're told), (a==0 || a > 1) reduces to a != 1, as many other posters have noted. – Graniteware

Stephen A. Lowe is correct. The original question stated that the integers were positive. Therefore, zero is not a permissible value. Thus, (a==0 || a>1) => (a > 1). It's elementary! – Shafer

I really can't believe so many people are missing this. I guess those crazy IEEE floats have confused people about how numbers work! – Shafer

@wasker.myopenid.com: a is a positive integer, that means it is greater than zero, so in the disjunction (a==0 || a>1) the term a==0 can never be true, leaving only a>1. – Overspread

@drhorrible.myopenid.com: we are told that all variables are positive integers, which means that a>0 not a>=0; the reduction to a!=1 is correct but incomplete, since a can never be less than 1. My initial assertion that N==0||N>1 yields N>=0 is, however, incorrect, since N cannot be 1. – Overspread

Answer 14

// 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. =]

Centralia

Answer 15

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.

Laoag

Answer 16

how is about the following logic, please comment it:

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

Cystolith

Answer 17

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)) 

Vinaya

NO! ((b - (a + p) == 0) || (b - (a + p) > 1)) DOES NOT EQUAL (b - (a + p) >= 0) !!! The correct reduction is: (b - (a + p) != 1) – Triglyph

a can == 0 so a > 1 woudln't suffice – Sweetbread

Answer 18

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;

Helli

this is the first one i've seen which actually works, but it's hard to call it a simplification... – Uria

Simplification for who? For the compiler or for the human? For the compiler there's no need. For the human just uses meaningful names instead of value1 and value2. – Helli

Answer 19

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.

Belia

b - (a + p) >= 0). this is not true; b - (a + p ) cannot be equal to 1 – Idelson

;) and why did you escape the a > 1 part in "(a == 0 || a > 1)" statement. – Idelson

@yapiskan - If I'm assuming that ((a + p) <= b) when (b = p) and (a = 0) then there is no reason to check to see if (a > 1) as the equation would then allow for ((a + b) <= b) where (a > 1), which is clearly false. – Belia

Answer 20

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).

Rhythmics

Won't a script process the &&'s conditionally anyhow...i.e. if it's A && B && C, it'll stop processing once one of them is false. substituting || just means it will stop if the first one is false, or if one of || terms is true. Not sure how this is an improvement. – Tiemannite

Good point. 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). – Rhythmics

Answer 21

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)

Dore

"Assuming the positive range includes the 0 value". Can we also throw in the square root of negative one? Because it's a cool number too! – Shafer

It is not an integer though ;) – Dore

Answer 22

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

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

Eudoxia

@PEZ: no, it isn't. positive integers start at 1. see mathworld.wolfram.com/PositiveInteger.html or wiki.answers.com/Q/What_is_a_positive_integer – Overspread

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.

Ape

Answer 24

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.

Cystolith

a is a positive integer, which means a>0 not a >= 0 – Overspread

Answer 25

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.

Bantamweight

Answer 26

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

Writeoff

Answer 27

(((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)**

Monochrome