Robert Eisele
Engineer, Systems Architect and DBA

Improving Interval Conditions

Checking if a certain number \(x\) falls into a given range between \(a\) and \(b\) is a quite easy task:

\[a \leq x \leq b\]

which can be implemented by taking the interval apart:

\[a <= x \&\& x <= b\]

What if \(a\) and \(b\) share common terms? You could change the condition in a way of balancing the terms over the equation in order to minimize the number of operations needed. The cool thing is, you can re-format an interval check as an expression with an absolute value and might be lucky to reduce the number of operations even further. Here is how it's done. Let \(a, b, x \in\mathbb{R}\):

\[\begin{array}{rl}& a \leq x \leq b\\\Leftrightarrow & 0 \leq x - a \leq b - a\\\Leftrightarrow & -\frac{b-a}{2} \leq x-a-\frac{b-a}{2} \leq \frac{b-a}{2}\\\Leftrightarrow & -\frac{b-a}{2} \leq x-a-\frac{b-a}{2} \land x-a-\frac{b-a}{2} \leq \frac{b-a}{2}\\\Leftrightarrow & -(x-a-\frac{b-a}{2}) \leq \frac{b-a}{2} \land x-a-\frac{b-a}{2} \leq \frac{b-a}{2}\\\Leftrightarrow & |x-a-\frac{b-a}{2}| \leq \frac{b-a}{2}\\\Leftrightarrow & |2(x-a)-(b-a)| \leq b-a\\\end{array}\]

This looks way more complicated than the previous check, but depending on how complex \(a\) and \(b\) is, it can shrink down the equation quite a lot. I now was wondring, if we can express \(a<x<b\) and \(a\leq x \leq b\) as an absolute value, would it be possible to express a range check with mixed operators the same way? Like \(a<x\leq b\) and \(a\leq x < b\). Obviously, this can hold only for \(a,b,x\in\mathbb{Z}\):

\[\begin{array}{rl}& a < x \leq b\\\Leftrightarrow & a < x < b + 1\\\overset{*}{\Leftrightarrow} & |2(x-a)-(b+1-a)| \leq (b+1)-a\end{array}\]

Again: The result looks more complicated than the one we started with, but it can be simplified a lot in some cases.

Give me an example

Let's say you want to plot a 11 by 6 pyramid on the console in one rush and only need to decide if a white-space is printed for the current line or a printable character:

for (i = 0; i < 6; i++) {
  for (j = 0; j < 11; j++) {
     print COND(i, j) ? 'X' : ' '
  }
  print '\n'
}

You need to formulate a range-check based on the variables \(i\) and \(j\). You can argue, that the following checks are needed to print a pyramide:

i: range
0: 4,6
1: 3,7
2: 2,8
3: 1,9
4: 0,10

Which result in the range check: \[4-i < j \&\& j < 6+i\]

Re-formulating this with the formula we just derived:

\[\begin{array}{rl}& |2(j-(4-i))-((6+i)-(4-i))| < ((6+i)-(4-i))\\=& |j-5| < i + 1\\=& |j-5| \leq i\\\end{array}\]

Bitwise-OR Trick

When bitwise OR-ing together two natural numbers \(x\) and \(y\), all bits set on both numbers will be set on the result as well. The idea now is, when OR-ing the numbers where \(y\) is of the form \(y:= 2^k-1\), the result will always be \(2^k-1\) as long as \(x\leq 2^k-1\), which means that \(x | (2^k-1) = 2^k - 1\Leftrightarrow a\leq 2^k-1 \forall k\in\mathbb{N}\).

We can extend this idea to \(x | ((2^j - 1)-(2^i - 1)) = 2^j - 1\). It turns out that when we get an interval \([a, b]\) and \(b+1\) is a power of two (like 1, 3, 7, 15, ...) as well as \(b-a\geq 0\) is a power of two, we can rewrite the interval-check to

\[x | (b - a) = b\]

For example \(12\leq x\leq 15\) is then \(x | 3 = 15\).

Draw examples

Height Width Expression

Other Examples:

You might also be interested in the following

31 Comments on „Improving Interval Conditions”

Getting A Loan
Getting A Loan

online loans for bad credit loans payday loans bad credit small payday loan

Quick Loan
Quick Loan

loan bad credit a loan with bad credit loan bad credit loans

Loans Online
Loans Online

loans denver payday loans loans payday loans bad credit

Paydayloan
Paydayloan

need a loan with bad credit payday loans for bad credit payday loans bad credit loan with bad credit

Loans
Loans

loans loans with bad credit payday loans for bad credit loans

Best Payday Loan
Best Payday Loan

bad credit loan loans loans loans for bad credit

Speedycash
Speedycash

loans loan for bad credit loans for people with bad credit bad credit loans

Payday Loan Online
Payday Loan Online

bad credit loan online installment loans direct lenders bad credit loan cash america payday advance

Loans Online
Loans Online

loans bad credit payday loans fast loans no credit check loans

Pay Day Loans
Pay Day Loans

loans with bad credit loans easy loans no credit loan for bad credit

Bad Credit
Bad Credit

loan bad credit loans with bad credit payday loans for bad credit loans

Best Payday Loan
Best Payday Loan

loans loans for people with bad credit loan bad credit loans

Payday
Payday

need a loan with bad credit loan for bad credit loans bad credit loan

Direct Lender Loans
Direct Lender Loans

loan for bad credit easy installment loans online online installment loans direct lenders check city payday loans

Online Payday Loan
Online Payday Loan

payday loans surrey bc loans loans no employment verification payday loan

Loan Cash
Loan Cash

online loans bad credit loans louisiana bad credit payday loans loans with bad credit

Speedy Cash
Speedy Cash

online loans for bad credit loans for bad credit loans apply online

Direct Lenders
Direct Lenders

payday loan application loans payday loans bad credit loans

Pay Day Loan
Pay Day Loan

online loans for bad credit loans for bad credit online loans bad credit loans

Personal Loans
Personal Loans

payday loans bad credit a loan with bad credit need a loan with bad credit payday loan providers

Online Loans
Online Loans

loans loans for people with bad credit bad credit loans reviews bad credit loans reviews

Instant Online Loans
Instant Online Loans

need a loan with bad credit bad credit payday loan lenders loans bad credit loans

Cash Loan
Cash Loan

get a loan with bad credit small payday loan online loans for bad credit bad credit payday loans

Speedycash
Speedycash

tribal loans guaranteed approval payday loan near me loan with bad credit loans

Speedycash
Speedycash

loans bad credit lender for bad credit loan bad credit fast personal loans

Cash Advance
Cash Advance

need a loan with bad credit loans bad credit loans loans

Online Payday Loans
Online Payday Loans

payday loans surrey bc personal loans unsecured loans loans

Best Payday Loan
Best Payday Loan

loans with bad credit loans for bad credit loans loans for bad credit

Quick Loan
Quick Loan

loans loans loans bad credit loans guaranteed

Paydayloan
Paydayloan

loans loans loan bad credit online loans bad credit

Online Payday Loan
Online Payday Loan

best loans for bad credit online loans for bad credit best cash advance loans online loans for bad credit

Leave a comment

4 / 2