Folding multiple (discrete) operations into one (continuous) operation

Question

For a simple example, suppose we're checking whether a char c is alphanumeric:

if (48 <= c && c <= 57 ||
    65 <= c && c <= 90 ||
    97 <= c && c <= 122)
{
    // ...
}

6 operations to confirm that it is.

But, doesn't there exist a continuous function f(c) such that f(c) > 0 for the alphanumeric byte values, and < 0 for the rest? I think there is at least one: a polynomial of degree 12, that "fits" 12 points, weaving up and down the x-axis; but maybe there exists a function of smaller degrees, too, or even non-polynomials. Such a formula would "simplify" the operations to:

if (f(c) > 0)
{
    // ...
}

Is there a term of art for this? (The word "folding" comes to mind, but it doesn't yield any relevant search results—only Haskell's concept of folding.) It seems that as long as we can map the codomain of a set of operations to a codomain of sufficiently finer granularity, we can obtain such a "fold". My question, then, is: can "folding" save time? Or is there some principle of conservation that forces the cost of computing a "fold" to match (or even exceed) the cost of computing the original, "crude" operations.

Answer 1

The polynomial intersects the x-axis 6 times, i.e. it has 6 real roots, so a degree-6 polynomial is enough.

f(c) = -(c-48)*(c-57)*(c-65)*(c-90)*(c-97)*(c-122)

This of course will waste time, doing 5 multiplications is much slower than 5 logical operations. Furthermore, && and || are short-circuiting so often you don't need to do all of them.

Answer 2

In your particular case, the optimal form is:

unsigned u = c;
if (u-48<10 || (u|32)-97<26)

Granted this does not solve the problem the way you were looking to, but the same concepts (i.e. (1) turning two comparisons against a range into one unsigned subtraction and comparison, and (2) using bitwise-or to combine multiple range checks whose lengths are the same and for which the alignments match like this) can often be generalized to other situations.

Answer 3

Is there some reason that the function isalnum() doesn't suffice for your needs? Don't forget to #include <ctype.h>.