5
$\begingroup$

I want to make a non-complex (for algorithmic implementation) logical condition to test whether some real interval contains any integer points.

Let $x$ be an interval with bounds $l, r$;

Let $LI(x)$ be a predicate that holds if $x$'s left boundary is inclusive and $RI(x)$ be a predicate that holds if $x$'s right boundary is inclusive.

Finally, let $P(x)$ be a predicate which holds if $x$ does contain at least one integer point.

Here's what I have produced so far:

$P(x) \equiv (\lfloor l \rfloor + 1 < r) \lor (RI(x) \land (r \in \mathbb Z) ) \lor (LI(x) \land (l \in \mathbb Z))$

Is this insufficient or superfluous? Can anyone make up a better formula? Thank you!

  • 0
    Yes $i$ndeed, thank you.2011-05-23

3 Answers 3

6

Edit: fixing condition for the open set using proposal in comments.

Given that the interval $x$ is not empty, the open interval $(l,r)$ contains an integer if and only if:

$\lfloor l \rfloor + 2 \leq \lceil r \rceil$

Otherwise, the only way for an integer to be in the interval is if one of the boundaries is closed, and that value is an integer. That is:

$(LI(x) \land \lfloor l \rfloor = l) \lor (RI(x) \land \lceil r \rceil=r)$

I use floor and ceiling here just to be cute - so we only need to compute $\lceil r \rceil$ and $\lfloor l \rfloor$.

So the full expression is: $(\lfloor l \rfloor + 2 \leq \lceil r \rceil) \lor$ $(LI(x) \land \lfloor l \rfloor = l) \lor $ $(RI(x) \land \lceil r \rceil=r)$

If you need the condition that $x$ is not empty, then $\land$ the above expression with $l\lt r \lor (l = r \land LI(x) \land RI(x))$

  • 0
    Yes, it is redundant! You only need to retain it i$f$ you weaken the latter inequality to include the closed interval with integer endpoint cases (by disjunction).2011-05-24
2

I would go with $ P = (|x|>1) \vee(\lceil l\rceil \leq r \wedge LI) \vee (l \leq \lfloor r\rfloor \wedge RI) $ Checking $|x|>1$ first, that is, $r-l>1$, is quite a good idea for when implementing this as an algorithm, chances are this condition will be true most of the time anyway, and with a good branch prediction the algorithm only costs one subtraction and one comparison, which makes it very fast.


The only trouble is it doesn't work for $x=\,].9,1.1[$... you need one extra logical summand, $ P = (|x|>1) \vee (LI \wedge \lceil l\rceil \leq r) \vee (RI \wedge l \leq \lfloor r\rfloor ) \vee (\lceil r\rceil - \lfloor l\rfloor =2) $ ok, now it's longer that your original proposal... not so nice. It should still be faster as an algorithm, though.


$LI \wedge \lceil l\rceil \leq r$ means: if the left border value is inclusive, it's sufficient to know if the number next to the right side of $l$ is in the interval, that is, to know that this number is not further to the right than $r$.

  • 0
    Could you please explain what the second and the third clauses mean?2011-05-23
0

$ (\lfloor l(x) \rfloor \neq \lfloor r(x) \rfloor) \vee (LI(x) \wedge \lfloor l(x) \rfloor = l(x)) \vee (RI(x) \wedge \lfloor r(x) \rfloor = r(x)) $