Math from scratch, part eleven: integer division

Now we come to the controversial one. As I pointed out back in 2011, the % operator is the remainder operator. When extending the division and remainder operators from naturals to integers, I require that the following conditions be true for dividend x, non-zero divisor y, quotient q and remainder r:

  • x == y * q + r
  • if x and y are non-negative then 0 <= r < y
  • (-x) / y == x / (-y) == -(x / y)

Let’s take a look at the consequences of these three facts. Continue reading

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. Continue reading

Math from scratch, part eight: integers

The integers are an extension to the naturals that closes them over subtraction. Rather than do anything fancy, I’m simply going to say that an integer is a natural with an associated sign, and that zero is always “positive”. We don’t want to end up in a situation where there are two forms of zero, since that is confusing. (We could of course have three signs, positive, negative and zero, but, meh. We don’t gain any great benefits from having a third sign.)

This time however I’m going to make a struct. C# requires that default(SomeStruct), where all the fields are their default values, be a valid value of the type. The default should logically be zero, as it is with all the built-in number types. So rather than checking for null, as we did with the reference type Natural, I’m going to check the sign field for null, which will only be possible if we’ve got a default struct. We’ll simply replace that with zero. (I am in general opposed to modifying the formal parameters of a method; I prefer to treat them as read-only variables. I’ll make an exception in this case because it keeps the code short and clear.) Continue reading

Math from scratch, part seven: division and remainder

We have only two operators left, integer division and remainder. We’ve left the most complicated two operations for last, so let’s tread carefully here.

(Only two? I’m not going to do bit shifting operators; I don’t think of them as operations on natural numbers. If you want them, obviously they are trivial: shifting right is just taking the tail, shifting left is appending a zero bit as the new head. Similarly I am not going to implement the bitwise logical operators. Nor am I going to do the unary plus operator, which wins my award for World’s Most Useless Operator. It is a no-op on both naturals and integers; if you really want it, it’s not hard to write. The unary minus operator makes no sense on naturals; the only legal operand value would be zero.) Continue reading

Math from scratch, part six: comparisons

Getting equality correct is surprisingly tricky in C#. The landscape is a bit of a confusing jumble:

  • The == and != operators are a syntactic sugar for static method calls, so it is dispatched based on the static (compile-time) type of both operands.
  • object.Equals(object) is a virtual method, so of course it dispatches on the runtime type of its receiver but not its argument. An override on a type T is required to handle any object as an argument, not just instances of T.
  • IEquatable<T>.Equals(T) by contrast takes a T.
  • For reference types, you’ve got to consider comparisons to null even if it is an invalid value.

That’s four ways to implement equality already and we haven’t even gotten into IComparable<T>.CompareTo(T), which also needs to be able to compute equality. Continue reading

ATBG meets math from scratch

In a nice bit of synchronicity my article this week on Ask The Bug Guys, our continuing series on the Coverity Development Testing Blog, is about the differences between the C, C++ and C# interpretation of the ++ operator[1. And of course everything in there applies equally well to the -- operator.] So read that first, and then it will make perfect sense why the increment operator on my Natural class from last time is simply:

public static Natural operator ++(Natural x)
{
  if (ReferenceEquals(x, null))
    throw new ArgumentNullException("x");
  return Add(x, One);
}

As always, if you have a question about a bug in a C, C++, C# or Java program please email it to TheBugGuys@coverity.com along with a concise reproducer of the problem if possible. We can’t answer every question but we’ll pick a sample of the most interesting ones a post an analysis on the dev testing blog.

Next time on FAIC: multiplication.

Math from scratch, part three: natural addition

Last time in this series we built a Natural object that represented a number as a linked list of bits, with the least significant bit in the head and the most significant bits in the tail. We use the “null object pattern” where a Zero tail represents that the remaining bits in the sequence are all zero, and the sequence of bits never ends in a zero bit followed by Zero.[1. If that sounds different than what I wrote the last time, reread last week’s post. I slightly changed the organization of the structure based on a reader suggestion.]

So let’s then divide our implementation into two parts, one which enforces the public part of the contract that null is meaningless:

Continue reading