Fastest Way to Determine If an Integer Is Between Two Integers (Inclusive) With Known Sets of Values

Fastest way to determine if an integer is between two integers (inclusive) with known sets of values

There's an old trick to do this with only one comparison/branch. Whether it'll really improve speed may be open to question, and even if it does, it's probably too little to notice or care about, but when you're only starting with two comparisons, the chances of a huge improvement are pretty remote. The code looks like:

// use a < for an inclusive lower bound and exclusive upper bound
// use <= for an inclusive lower bound and inclusive upper bound
// alternatively, if the upper bound is inclusive and you can pre-calculate
//  upper-lower, simply add + 1 to upper-lower and use the < operator.
    if ((unsigned)(number-lower) <= (upper-lower))
        in_range(number);

With a typical, modern computer (i.e., anything using twos complement), the conversion to unsigned is really a nop -- just a change in how the same bits are viewed.

Note that in a typical case, you can pre-compute upper-lower outside a (presumed) loop, so that doesn't normally contribute any significant time. Along with reducing the number of branch instructions, this also (generally) improves branch prediction. In this case, the same branch is taken whether the number is below the bottom end or above the top end of the range.

As to how this works, the basic idea is pretty simple: a negative number, when viewed as an unsigned number, will be larger than anything that started out as a positive number.

In practice this method translates number and the interval to the point of origin and checks if number is in the interval [0, D], where D = upper - lower. If number below lower bound: negative, and if above upper bound: larger than D.

Most efficient way to determine if value between two other values, inclusive

The first test:

(p - v1) * (p - v2) <= 0

May result in overflow or underflow, due to the arithmetic operations.

The last one:

p < v1 != p < v2

Doesn't provide the same results as the others, which are inclusive in respect of the boundaries v1 and v2. It's an admittedly small difference, considering the range and precision of the type double, but it may be significant.

Another option is to explicitly expand the logic of the second function:

p <= std::max(v1, v2) && p >= std::min(v1, v2)     // v1 and v2 are compared twice

Into something like this:

bool inRangeComp(double p, double v1, double v2) {
    return v1 <= v2                                // <- v1 and v2 are compared only once
        ? v1 <= p && p <= v2 
        : v2 <= p && p <= v1;
}

At least one compiler (gcc 8.2), HERE (thanks to jarod42 for the linked snippet), seems to prefer this version over the alternatives.

Fastest way to check if a list of sets has any containment relationship

Seems to be faster to sort by length and then try small sets as subset first (and for each, try large sets as superset first). Times in ms from ten cases, data generated like you did but without seeding:

agree yours   mine  ratio  result
True   2.24   2.98   0.75  True
True 146.25   3.10  47.19  True
True 121.66   2.90  41.91  True
True   0.21   2.73   0.08  True
True  37.01   2.82  13.10  True
True   5.86   3.13   1.87  True
True  54.61   3.14  17.40  True
True   0.86   2.81   0.30  True
True 182.51   3.06  59.60  True
True 192.93   2.73  70.65  True

Code (Try it online!):

import random
from timeit import default_timer as time

def original(lst):
    checked_sets = []
    for st in lst:
        if any(st.issubset(s) for s in checked_sets):
            return True
        else:
            checked_sets.append(st)
    return False

def any_containment(lst):
    remaining = sorted(lst, key=len, reverse=True)
    while remaining:
        s = remaining.pop()
        if any(s <= t for t in remaining):
            return True
    return False

for _ in range(10):
    lst = [set(random.sample(range(1, 10000), random.randint(1, 1000))) for _ in range(10000)]
    t0 = time()
    expect = original(lst)
    t1 = time()
    result = any_containment(lst)
    t2 = time()
    te = t1 - t0
    tr = t2 - t1
    print(result == expect, '%6.2f ' * 3 % (te*1e3, tr*1e3, te/tr), expect)

Improvement

The following seems further ~20% faster. Instead of first comparing the smallest set with potentially all larger sets before giving even just the second-smallest a chance, this does give other small sets an early chance.

def any_containment(lst):
    sets = sorted(lst, key=len)
    for i in range(1, len(sets)):
        for s, t in zip(sets, sets[-i:]):
            if s <= t:
                return True
    return False

Comparison with my old solution (Try it online!):

agree  old    new   ratio  result
True   3.13   2.46   1.27  True
True   3.36   3.31   1.02  True
True   3.10   2.49   1.24  True
True   2.72   2.43   1.12  True
True   2.86   2.35   1.21  True
True   2.65   2.47   1.07  True
True   5.24   4.29   1.22  True
True   3.01   2.35   1.28  True
True   2.72   2.28   1.19  True
True   2.80   2.45   1.14  True

Yet another idea

A shortcut could be to first collect the union of all single-element sets, and check whether that intersects with any other set (either without sorting them, or again from largest to smallest after sorting). That likely suffices. If not, then proceed as previously, but without the single-element sets.

What is the fastest way to calculate the logical_and (&&) between elements of two __m256i variables, looking for any pair of non-zero elements

You can cleverly combine a vpcmpeqq with a vptest:

__m256i mask = _mm256_cmpeq_epi64(a, _mm256_set1_epi64x(0));
bool result = ! _mm256_testc_si256(mask, b);

The result is true if and only if (~mask & b) != 0 or

((a[i]==0 ? 0 : -1) & b[i]) != 0 // for some i
// equivalent to
((a[i]==0 ? 0 : b[i])) != 0      // for some i
// equivalent to
a[i]!=0 && b[i]!=0               // for some i

which is equivalent to what you want.

Godbolt-link (play around with a and b): https://godbolt.org/z/aTjx7vMKd

If result is a loop condition, the compiler should of course directly do a jb/jnb instruction instead of setnb.

How works with large integers?

I've seen variations of this issue come across this forum, and keeping with the comments, one should utilize the acquisition of numbers as large as credit card numbers via the entry of a string value. Ultimately, you will probably need to validate the entered number via the Luhn algorithm, so keeping that in mind here is a proof of principle snippet of code that requests a credit card number entry (as a string), and then validates whether or not the entry is valid using the Luhn algorithm.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int check_valid(char * num)
{
    int sum = 0;
    int work = 0;
    char card[20];

    if ((strlen(num) %2 == 0))  /* Even numbers - do not need a leading zero */
    {
        strcpy(card, num);
    }
    else                        /* Odd numbers - add a leading zero to evaluate */
    {
        strcpy(card, "0");
        strcat(card, num);
    }

    printf("Length of number is: %d\n", (int)strlen(num));

    for (int i = 0; i < strlen(card); i++)
    {
        work = card[i] - '0';
        if ((i %2) == 0)
        {
            work = (card[i] - '0') * 2;
            if (work > 9)
            {
                work = work - 9;
            }
        }
        sum = sum + work;
        printf("Digit is: %d Value is: %d Sum is %d\n", (card[i]- '0'), work, sum);
    }

    return ((sum % 10) == 0);
}

int main()
{
    char number[20];
    int x = -1;

    printf("Enter a number: ");
    x = scanf("%s", number);

    x = check_valid(number);

    if (x == 0)
        printf("Invalid\n");
    else
        printf("Valid\n");

    return 0;
}

This particular example utilizes the "scanf" function, but one could use the "fgets" function. It usually boils down to preference. But once the value is entered, the individual digits can be evaluated.

Give that a try to see if that meets the spirit of the project.

---

Related Topics