1
$\begingroup$

The C memcmp function (and strcmp) does a comparison similar to the function below for comparing integers:

int compare(const int a, const int b) {
     if (a > b) return 1;
     if (b > a) return -1;
     return 0;
}

Microsoft information for their strcmp says:

The strcmp function performs an ordinal comparison of string1 and string2 and returns a value that indicates their relationship.

The manual of GNU's libc describes the comparison in this way:

Your comparison function should return a value the way strcmp does: negative if the first argument is "less" than the second, zero if they are "equal", and positive if the first argument is "greater".

But doesn't define any name for this comparison type.

What is the name for this comparison algorithm?

And why doesn't memcmp simply return say 0 if a and b the same and 1 otherwise?

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ Your last question is equivalent to "Why do we have < and > instead of just !=?" Isn't the answer obvious? $\endgroup$ – David Richerby Mar 4 '18 at 14:15
  • $\begingroup$ @DavidRicherby: What isn't obvious is whether the value of having memcmp indicate which operand is "higher" is worth the cost. For many usage scenarios, it would be more helpful to have a variation of memcmp which reported the location of the first mismatch, and a pass-fail version for situations where the blocks are expected to match (implying that vectorization is likely to be worthwhile, and that if examining a later part before an earlier part would be convenient, and it is found not to match, there's no need to examine the earlier part at all). $\endgroup$ – supercat Feb 24 at 20:16
3
$\begingroup$

The question is about a three-valued function in a situation where a boolean is often used (eg <=). I personally refer to this as the sign or signum: the sign of the difference of the comparands. However I have not seen a widely-used term; the best supportable answer I can give is that there is none.

In Quicksort, when a three-way partition (based on this "signum") is used instead of two-way, it's called ternary (and there are ternary search trees based on the same distinction), but that's about as specific as it gets.

My reasoning behind my naming this quantity signum is that comparison is often implemented as subtraction; the CMP instruction is essentially a SUB instruction that discards the actual result but retains the sign and zero flags.

Strings are obviously not numbers, but they have a commonly-used embedding into [0,1) that makes lexicographic comparison equivalent to subtraction and signum extraction.

As to the idea of a two-valued (==, !=) predicate, there is some precedent for this idea in contexts where the signum may not be obtainable. Fagerbergh, Pagh et al. construct what they call a "unordered trie" on hashed string values, where the original order of the strings is obscured due to hashing, but the position where they first disagree is still known. This practice also has some use in applying collations, where only the branching character needs to be looked up to get the collated order (the equal prefix is skipped).

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

You said:

And why doesn't memcmp simply return say 0 if a and b the same and 1 otherwise

As the comparison of two numbers or strings has three states, we should specify the state of the comparison. The statement is correct when we are seeking about the equality not the comparison in general term.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.