The multiplicative complexity of interval checking

Thomas Häner, Mathias Soeken

We determine the exact AND-gate cost of checking if $a\le x<b$, where $a$ and $b$ are constant integers. Perhaps surprisingly, we find that the cost of interval checking never e…