Robert Eisele
Systems Engineer, 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}\]

Draw examples

Height Width Expression

Other Examples:

You might also be interested in the following

Leave a comment

2 + 10