(Last Mod: 27 November 2010 21:38:38 )
Relationship to Subtraction (optional material)
These operators perform the standard relational operations that most people are long familiar with.
A relational expression produces a logical result. A logical result has one of two possible values - if the relationship indicated by the operator is False, then the result is an integer 0 while if the relationship is True the result is an integer 1.
The relational operators are frequently represented by two-letter operators in many assembly languages and so those designators are used here. Although rather obvious upon examination, the common names associated with each are:
| Operation | Operator | Level | Assoc | Syntax | Evaluates to |
| LT | < |
6 |
L |
A < B |
O if FALSE
|
| GE | >= |
A >= B |
|||
| GT | > |
A > B |
|||
| LE | <= |
A <= B |
|||
| EQ | == |
7 |
A == B |
||
| NE | != |
A != B |
Perhaps the most common mistake made by new programmers is to write a statement similar to the following:
if (10 < k < 100)
When they want the test expression to evaluate to True if the value of k is between 10 and 100. But while this is what they want, it is not what they wrote. Remember that these are operators that return a value of 0 (False) or 1 (True) based on a comparison of two operands. Because these operators are left-associative, the above expression is equivalent to:
if ( (10 < k) < 100)
The inner expression will return a value of either 0 or 1 and since either one of these is less than 100, the outer expression will always evaluate to True.
The key is to understand that the original version that was attempted is really a shorthand expression that humans use to represent a more complicated relationship. The form of the shorthand makes the expression more meaningful to humans given they way we perceive things, but computers have to take things one operator at a time. The full logical relationship implied by the original expression is that k must be greater than ten and it must be less than one hundred in order for the expression to be true. So, write the expression the expresses the full relationship:
if ( (10 < k) && (k < 100) )
Although we generally interpret the result of relational expressions as being True or False, the fact remains that they are integers and can be used as integers. Consider the following examples:
Example 1: Count the number integer squares between 1 and 100 that are less than the value stored in n.
count = 0;
for(i = 1; i <= 100; i++)
count += ( i*i < n );
Example 2: Set limit equal to the max limit if k is greater than max, otherwise use the default limit.
limit = defaultlimit + (k > max)*(maxlimit - defaultlimit);
In the above example, we are using the relational operator as a switch to turn the second term on or off. If the test fails, only the first time survives while if the test passes the second term is turned on and it is written in such a way that it subtracts off the first term and replaces it with the value in maxlimit.
Example 3: If limit to the default limit or 50% greater than the default limit if k is greater than max.
limit = defaultlimit( 1 + 0.5*(k > max));
The term complementary, in everyday usage, commonly means "the opposite of" or "having what the other lacks". In the context of this discussion, we use it to mean precisely that. Two operators are complementary if and only if the results obtained by using one is always the opposite that would be obtained using the other. Always. Not might be, not sometimes, not most of the time, not in all but one special case - always.
The six relational operators form a set of three complementary pairs as follows:
| Complementary Pairs | |
EQ == |
NE != |
LE <= |
GT > |
GE >= |
LT < |
People tend to think of "less than" as being the opposite of "greater than". It isn't. Repeat twenty times, "No matter how attractive the notion is, 'less than' is not the opposite of 'greater than' - it just ain't so!"
But why not? What if the two values being compared are equal? Then both operators yield False. Similarly, if LE and GE are used instead with operands that are equal, both will produce a result of True. Remember, two operators are complements of each other if and only if they produce the opposite results every time - most of the time simply doesn't count.
We harp on this point for two reasons - first, it has proven to be a very difficult notion for many people to grasp and, second, not grasping it can lead to many subtle and hard to locate logic errors.
Example 4: Perform the same logic as Example 2 using a conditional operator.
limit = (k > max)? maxlimit : defaultlimit;
Example 5: Rewrite the conditional of Example 4 with the values reversed.
limit = (k <= max)? defaultlimit : maxlimit;
In this case, we may simply have preferred to have the default limit (presumably the lower value) appear before the maximum limit. We could do this by using the complimentary operator - which is LE and not LT.
If we have the expression:
putc( (x==y)? '=' : '!', stdout);
putc('=', stdout);
Then what we expect to see are the characters "==" if
the two values are equal and "!=" if they are not. This
will work very reliably if x and y are integers. But if one or both are
floating point data types, it will almost always claim that the two values are
not equal.
Why?
Because the two values will almost always be unequal!
Why?
Because the equality (and its compliment) are take us very literally when we ask if two values are equal. If we are using a double point representation that can represent 16 significant digits in a floating point value, then two such values are equal if and only if they match to all sixteen digits - if the very last digits don't match, then the two values are not equal. Period. End of discussion.
To give an idea of the scale of agreement required to be considered equal, if we stored the value for the weight of the aircraft carrier U.S.S Nimitz (91,300 tons) in one variable and the weight of her nominally identical sister ship the U.S.S. Carl Vinson in another, then if the values disagreed by more than ten micrograms they would be considered not equal. A drop of water from a typical eyedropper is approximately fifty times this amount.
Since there is almost always round off error in any floating point computation, it is virtually guaranteed that, unless we have been extremely careful in our computations based on a thorough knowledge of the behavior of the representation we are working with, that two values that should ideally be equal will not be.
So how do we determine whether the values in two floating point variables are equal? Simple, we invoke the notion of "close enough" - a concept which, by the way, digital computers fundamentally do not comprehend.
If asked whether the weight of two people were equal, you would probably answer yes if their weights agreed to within a tenth of a pound. So if the weight (in pounds) of person B is stored in variable Wa and the weight of person B is stored in variable Wb, you would want the difference between their weights to be less than a tenth of a pound. Our first attempt might be something like:
putc( ((Wa - Wb) < 0.1)? '=' : '!', stdout);
putc('=', stdout);
But what if Wa is 100 pounds and Wb is 240 pounds? Then Wa - Wb is -140 lbs and that is certainly less than 0.1 since any negative value is less than any positive value.
Thinking a bit more carefully, we realize that what we are really looking for is:
-0.1 < (Wa - Wb) < 0.1
By taking the absolute value of (Wa - Wb), we can use the rest of our expression. Let's write a function to answer the question of whether two floating point values are equal:
int isequal(double a, double b)
{
return ((a > b)?(a-b):(b-a)) < 0.1;
}
For lots of uses, this would work fine, but would we consider two golf balls to be of equal weight if they different by a tenth of a pound (the maximum weight of a golf ball is 0.101 lb). Would we require that two aircraft carriers have the same weight to within a tenth of a pound before we considered them to be of equal weight?
Why did we pick 0.1lb being a reasonable limit for declaring two people equal in weight? More than anything, it's because 0.1lb is approximately 0.1% of a light person's typical weight and if the weight of two objects agree to within 0.1%, then we are probably safe considering them to be of equal weight for most purposes.
There's nothing magical about 0.1%, but the concept is pretty universal - two values can be considered equal if they differ from each other by less than some percentage. To get the percentage they differ by, we take the difference and divide it by something - that something can reasonably be the average of the two values, the larger of the two values, or the smaller of the two values. Each choice has pros and cons and which we choose depends, in part, on whether our values must be positive or whether they might be negative and, trickiest of all, if one both values might be small with one being positive and the other being negative. Which we choose needs to be based on considering what, for our purpose, it means for two values to be equal in each of possible case we might have to deal with.
For our general use function here, we will use the following: Two values are equal if they differ by less that some percentage of the magnitude of the value that is largest in magnitude.
#define ISEQUAL_TOL (0.1)
int isequal(double a, double b)
{
double m1, m2, diff;
diff = (a > b) ? (a-b) : (b-a);
m1 = (a < 0) ? -a : a ;
m2 = (b < 0) ? -b : b ;
return ISEQUAL_TOL > ( diff / ((m1 > m2)? m1 : m2)) ;
}
Most processors have a set of "status" bits that instructions can examine. While assembly language programs interact with these programs directly and extensively, high level programming languages frequently do not provide a means for doing so. With C, it is possible to interact directly, but this is highly processor-specific and therefore is not used unless the performance requirements are critical and, even then, the usual option is to write the critical parts of the program in assembly language.
But the techniques that are used by assembly language programmers are useful to know for they provide insight in how to use various properties and tricks to in order to solve a wide range of problems.
Two of the status bits that are often available are Z and S. The Z (ZERO) bit is set if the result of certain operations operation produce a result of exactly zero (all bits cleared in the register in question) and the S (SIGN) bit is set if a result of certain operations is negative. Of course, these bits may be called something else, may be encoded differently, or may not even be available - although other bits that serve other purposes can usually be used to get this same information. Did we mention that this is highly processor-specific?
Assuming that we have these two bits, Z and S, available and that they act as described, we can implement all of the relational operators using just subtraction and examining the state of these two bits:
| A - B | NEEDED OUTPUT FOR EACH OPERATOR | ||||||
| Z | S | LT | GE | GT | LE | EQ | NE |
| 0 | 0 | F | T | T | F | F | T |
| 0 | 1 | T | F | F | T | F | T |
| 1 | 0 | F | T | F | T | T | F |
| 1 | 1 | UNDEFINED / DON'T CARE | |||||
Since a result of a subtraction can't be both zero and negative (less than zero) at the same time, both Z and S can never be set simultaneously (at least not as the result of a subtraction operations - other operations may only affect the value of one bit in which case the other bit is meaningless). Hence we don't care what our operators produce under those conditions because they should never be asked to produce anything - we'll choose whatever result makes the logic implementation simplest.
The logical relationships become very simple, especially since we can use the properties of the complimentary pairs to generate half of the results from the other half:
The actual logic circuits that would implement these signals would almost certainly be different - although logically equivalent. The reason is that the certain logic operations are faster and require less silicon area than others, so the logic equations are written to exploit those operations.