Math from scratch, part ten: integer comparisons

I’m going to use the same technique I used for Natural comparisons to do Integer comparisons: make a helper function that returns -1 if x < y, 0 if x == y and 1 if x > y, and then have every entry point simply call that helper function. This way we know that all the operators are consistent. The big difference here of course is that I do not need to have a special case that says that null sorts before any value.

Of course a negative number is smaller than any positive number. If the two numbers are the same sign then we compare their magnitudes appropriately.

private static int CompareTo(Integer x, Integer y)
{
    if (x.IsDefault) x = Zero;
    if (y.IsDefault) y = Zero;
    if (x.sign == Negative && y.sign == Positive)
        return -1;
    else if (x.sign == Positive && y.sign == Negative)
        return 1;
    else if (x.sign == Positive)
        return x.magnitude.CompareTo(y.magnitude);
    else
        return y.magnitude.CompareTo(x.magnitude);
}

Notice that in the last case I am careful to not simply invert by taking the negative.

And now we can implement all the comparison entrypoints trivially, as we did before:

public int CompareTo(Integer x) { return CompareTo(this, x); }
public bool Equals(Integer x)   { return CompareTo(this, x) == 0; }
public static bool operator <(Integer x, Integer y) { return CompareTo(x, y) < 0; }
public static bool operator >(Integer x, Integer y) { return CompareTo(x, y) > 0; }
public static bool operator <=(Integer x, Integer y){ return CompareTo(x, y) <= 0; }
public static bool operator >=(Integer x, Integer y){ return CompareTo(x, y) >= 0; }
public static bool operator ==(Integer x, Integer y){ return CompareTo(x, y) == 0; }
public static bool operator !=(Integer x, Integer y){ return CompareTo(x, y) != 0; }
public override bool Equals(object obj)
{
    return (obj is Integer) && (CompareTo(this, (Integer)obj) == 0);
}

And of course we need an implementation of GetHashcode that matches the implementation of Equals, such that equal items always have equal hash codes:

public override int GetHashCode()
{
    Integer x = this;
    if (x.IsDefault) x = Zero;
    return (x.sign == Positive ? 1 : -1) * x.magnitude.GetHashCode();
}

All right, we have comparisons. Next time on FAIC: we’ll finish off the operators with division and remainder, and then we’ll do some more advanced arithmetic.

About these ads

12 thoughts on “Math from scratch, part ten: integer comparisons

  1. I might be being paranoid but i’d have gone for

    ((x.sign == Positive ? 1 : -1)*x.magnitude).GetHashCode();

    as that is obviosly the same as the equivalent int.GetHashCode();

  2. except I’m forgetting that magnitude is a Natural not an int so that won’t work and it is obvious given Natural.GetHashCode implementation why this works

  3. Don’t presume that the “comparision” operators are doing comparisons. The return type doesn’t have be a Boolean.
    See NuGet: Exts.Ranging.Classes.Operators

    If you implement an extension method over the constrained generics of T : IComparable you can lift it into a pseudotype that implements the traditional comparision operators.
    See NuGet: Exts.Comparisions.Classes.Operators

  4. Why not just swap the order of operands instead of the Invert function?
    “return y.magnitude.CompareTo(x.magnitude);” is less code and uses less built-in types.

  5. Pingback: The Morning Brew - Chris Alcock » The Morning Brew #1473

    • Are you referring to a particular one-line function in Eric’s code? If so, I’m not clear which one: most of the one-liners are the comparison operators. If you don’t write them, you don’t have overridden comparison operators, which is the point of the article.

      In general, I would vote yes, in at least the following circumstances:

      * As here, when you are overriding something, so you need a method with a particular name for it to do what you want. Whether that method is one line or many doesn’t matter.
      * If the logic, no matter how simple, is re-used in multiple places and should be consistent. IME low-level GUI code winds up full of these one-liners.
      * If the one-liner creates a distinction between public interface and private implementation. For instance, a class that made use of integer IDs may need a notion of an invalid ID. Internally, you know that the invalid ID is a const that equals -1, but that is hidden from the public interface. The public interface may be an IsValidId() method or a GetInvalidId() method or something. These would just be one-liners.
      * If a good choice of method name just makes it clearer what your one line of code is meant to achieve, when it would be too unclear otherwise.

    • When the abstraction provided by the function is meaningful and useful, then it is worth writing it. Whether it is a one-liner or not is only an implementation detail, subject to change.

  6. For a moment here I thought that multiplying by -1 was a poor way to handle negative numbers in GetHashCode(), because I remembered that the Dictionary class does not use the sign bit of the hash.
    Fortunately, it actually discards it using a bit mask, not a multiplication by -1. That means your GetHashCode() implementation does not collide every positive Integer with its negative counterpart.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s