2328

27
+24  Q:

## Can you simplify this algorithm?

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

+2  A:

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.

+1  A:

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.

Fails on a = 0, b = 2, p = 1
No, it does not fail. I just tested it. Both implementations return false on Function(0, 2, 1). Please retract that comment.
@TomWij: a cannot be = 0, it is a positive integer (which means > 0)
+5  A:

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.

Ha, downvotes for your totally correct and not at all wrong idea...
I'm reading Uncle Bob's Clean Code atm and this code could have been one of the before pictures for refactoring methods.
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.
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.
but extracting common expressions and encapsulating them behind another name removes the ability to eliminate subexpressions...
The key word you forgot was "meaningful" :)
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 ;-)
A:

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))
``````
That is wrong, you don't want (b - (a + p)) to be 1.
NO! ((b - (a + p) == 0) || (b - (a + p) > 1)) DOES NOT EQUAL (b - (a + p) >= 0) !!! The correct reduction is: (b - (a + p) != 1)
a can == 0 so a > 1 woudln't suffice
Fails on a = 0, b = 0, p = 0
A:

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;
``````
this is the first one i've seen which actually works, but it's hard to call it a simplification...
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.
Uh, you made it longer. xD
+4  A:
``````b >= p && b != p+1
``````

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

``````a != 1 && b >= a+p && b-a-p != 1
``````
How did you get rid of the "(a == 0 || a > 1)" part?
a is irrelevant. nevertheless, my solution doesn't work.
Second one works, good work. :-)
@TomWij: yeah, it turns out a isn't so irrelevant after all =))
A:

I think PEZ has it right.

I think Jake has it wrong about PEZ having it right.
He had. But I think Jake is right now. He's probably one of those ahead of things. =)
I think we should use "vote" or "comment" rather then answer to comment on answer.
Well, this answer once was an answer of it's own, but Jake edited that away. Besides, i think vote isn't the way to go here since vote-up means it's helpful and it can be helpful even if it's not the correct answer.
+2  A:

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

Fails on a = 0, b = 0, p = 1
@TomWij: a and b cannot be = 0, they are both positive integers (which means > 0)
since the original code includes "a == 0", then I think it's safe to assume he meant "non-negative integers", not "positive integers"
+16  A:

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.

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.
Huh. "Do not use brain"? Simplifying overcomplicated conditionals is not 'optimization', it is refactoring / improving clarity.
What if it isn't compiled? It could be in a script that doesn't optimize.
@Brian - 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.
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...)
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)
Your other points I agree with completely, and would probably not alter the formula.
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!
A:
``````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))

bap = b - (a + p)
return bap >= 0 and bap != 1 and a != 1
``````
fails on a = 9, b = 9, p = 9
Fails on a = 0, b = 0, p = 1
ok looks like you've fixed it!
How does it fail on those?
Ah, yeah, "=>" was a typo.
Fails on a = 0, b = 0, p = 1; fill in your equatation and in the question, it won't give the same boolean value.
this will only work if bap is a signed integer. otherwise bap will rollover to UINT_MAX.
For me it returns False in both cases.
yep i've just tested this on all combinations of 0-199 which is 8 million tests (overkill i know), and it works.
+37  A:
``````(a + p <= b) && (a != 1) && (b - a - p != 1);
``````
Passes my test (All possible combination of 0-200)
a+p<=b implies b>=p. a+p<=b => b>=p+a
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.
that a+b in my comment above should of course read a+p!
@[Brian Genisio]: did you try the combinations with some value near or equal to MAX_INT?
Actually, if we're talking about optimising here, then my variation with the OR in it and the reordering is probably even better.
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)
@[Andrea Francia] No, only 0-200. Some Max tests would be really useful, assuming the input range can approach Max.
@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.
After failing to reduce this further (and deleting my failed answer) I have to agree that this solution is optimal. +1
(a != 1) is simplest to evaluate and can be done first. @Brian's suggestion works for all combinations [0,600).
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?
@mercator, Woops, I copied the wrong thing. Well, I tested what he meant, and it was wrong (as you said).
please show your work, and explain a!=1 instead of a>1 given that a is a positive integer ;-)
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.
@PEZ: 0 is not a positive integer. But if we assume positive integers, then a!=1 is just as good as a>1 ;-)
A:
``````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;
}
}
``````
Way to go. EVen if I think "b - s > 1" is clearer.
No, doesn't work.
Using your test fixture, I do not get a failure on my solution, though you commented that It failed on 0,2,1
Clearer than "b - s - 1 > 0" that is.
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).)
Uh, people down vote too easily to my opinion. There is nothing wrong with my answer...
@TomWij, I agree.
doesn't casting to unit eliminate negative results? and thus possibly hide errors?
A:

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.

b - (a + p) >= 0). this is not true; b - (a + p ) cannot be equal to 1
@yapiskan - Opps, thanks for catching that
;)and why did you escape the a > 1 part in "(a == 0 || a > 1)" statement.
@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.
+2  A:
``````(a!=1) && ((b==a+p) || (b>1+a+p))
``````

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

+1  A:

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
``````
What language, pray tell?
A:

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

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

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.

A:

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)

"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!
It is not an integer though ;)
A:

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

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

A is allowed to be 0.
@PEZ: no, it isn't. positive integers start at 1. see http://mathworld.wolfram.com/PositiveInteger.html or http://wiki.answers.com/Q/What_is_a_positive_integer
A:
``````(((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)**
``````
+1  A:

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.

``````((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!"); }
}

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;
}
}
``````
@Steven: (a == 0 || a > 1) cannot be reduced to (a > 1). It's (a != 1).
@wasker - If we are assuming that 0 is neither negative or positive then (a > 1) and (a != 1) have the same truth table.
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.
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!
I really can't believe so many people are missing this. I guess those crazy IEEE floats have confused people about how numbers work!
@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.
@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.
A:

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

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

+1  A:
``````// 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. =]

A:

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.

a is a positive integer, which means a>0 not a >= 0
+1  A:

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.
``````
A:

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.