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.

Advertisements

13 thoughts on “ATBG meets math from scratch

  1. Hm. So, if I want to implement finite field (say, base 2^32) arithmetics, I cannot have in-place increment, even if I implement field elements as structs?

    • Sure you can, you just shouldn’t abuse the operators for it.

      People generally don’t expect that “x + 5” or “x++” changes the value of x and since C# doesn’t offer a += operator that would allow you to optimize for this case you’re probably better off with just implementing an add method.

        • Oh yes we have to be careful with semantics and definitions here. Certainly people expect x++ to change the value of the *variable* x, but just as you say not the object being pointed to.

          “x = IntWrapper(5); foo(x++)” should still cause an IntWrapper(5) object being passed to foo after all (just making up a hopefully obvious example class).

          And due to that expectation it’s just impossible to implement x++ in-place.

      • …and hope that the optimizer will eliminate redundant copying. Yeah. Good luck working with 10000-by-1000 matrices of 16 byte-sized values, because allocating 160 MB of memory at every addition is not cheap!

        • My maths is rusty, but in the ring/field/whatever of 32-bit signed integers -858993459 * 5 = 1. With unsigned integers 3435973837 * 5 = 1.

          In both cases 5 does have a multiplicative inverse.

          • Wow, I am actually ashamed. Should’ve thought a bit before pointing at a random number and claiming it’s not invertible. Yes, of course 5 is a unit since 5 and 2^32 are coprime; but what about 2? Or any other natural power of two? Or any even number whatsoever? They divide zero (2 * 2^31 = 0, 10 * (-2147483648) = 0), and a zero divisor can’t have a multiplicative inverse (in associative rings at least).

            So it’s still not a field, because half of the elements have no multiplicative inverse.

        • Someone else corrected me elsewhere about Z(compositeNumber) being a ring rather than a field, so it’s probably a common point of confusion. As for built-in integer types being finite ring, that’s mostly true in C# unchecked numeric contexts, but not quite. In situations involving type conversions, C# often regards them as numbers. Personally, I think a lot of numeric-handling confusion would be best avoided by having separate storage-location types for integers that behave as numbers and ones that behave as rings; an operation between a number and a ring element would yield an element of that same ring, as would an operation between two operands of matching ring types. Operations between mismatched ring operands should be forbidden (unless one of the elements is converted to a number). Such a thing could probably be added to .NET languages without affecting the runtime by defining attributes that could be applied to public members to indicate how compilers should interpret them [e.g. regardless of whether checked arithmetic is enabled, if a function has an `int` return type explicitly tagged as a number and it returns -2000000000, subtracting 1000000000 from it should throw an OverflowException; if it were tagged as a ring member, it should yield -852516352]. There would be no need for separate .NET types to define the “number” and “ring” variants of each integer type, since one can’t perform any arithmetic upon boxed or generic integer types without first converting them to known integer types.

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