Math from scratch, part four: natural multiplication

Last time in this series proper we implemented integer addition recursively; today we’ll jump right in and go to multiplication. Continue reading

Advertisements

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

Math from scratch, part two: zero and one

Last time I said that I was going to choose the “sequence of bits” technique for representing a natural number. At this point I don’t think I need to go into detail about how bits work; you all know that each position represents the addition of a power of two multiplied by the value of the bit at that position, blah blah blah. Let’s instead concentrate on the technical details. Continue reading

Math from scratch, part one

Computers are of course called “computers” because they’re good at math; there are lots of ways to do math in C#. We’ve got signed and unsigned integers and binary and decimal floating point types built into the language. And it is easy to use types in libraries such as BigInteger and BigRational[1. Which can be found in the Microsoft Solver Foundation library.] to represent arbitrary-sized integers and arbitrary-precision rationals.

From a practical perspective, for the vast majority of programmers who are not developing those libraries, this is a solved problem; you can use these tools without really caring very much how they work. Sure, there are lots of pitfalls with binary floats that we’ve talked about many times in this blog over the years, but these are pretty well understood.

So it’s a little bit quixotic of me to start this series, in which I’m going to set myself the challenge of implementing arbitrary-size integer[2. Maybe we’ll go further into rationals as well; we’ll see how long this takes!] arithmetic without using any built-in types other than object and bool.[3. As we’ll see, we’ll be forced to use int and string in one or two places, but they will all be away from the main line of the code. I will also be using the standard exception classes to indicate error conditions such as dividing by zero.]

Continue reading

ATBG: Reflection and default parameters

We have two posts today on the Coverity Development Testing Blog‘s continuing series Ask The Bug Guys. First, my colleague Jon explores a tricky difference between the 1989 and 1999 C standards involving conversions of array types to pointer types that can cause undefined behavior if you’re not careful. Then I discuss why Reflection and constructors (or any other method, for that matter) with default parameters do not play nicely with reflection.

Thanks to readers Dennis and Laurence for these interesting questions. If you have a question about a bug in your C, C++, C# or Java program, please send it to TheBugGuys@coverity.com; we’d love to see it. We can’t guarantee an answer to all your problems, but we will pick a selection of the best questions and post about them on the development testing blog. Past episodes can be found here, and the RSS feed for the blog is here.

Verbatim identifiers

In C# you can preface any identifier or keyword with the @ symbol to make it a verbatim identifier. This allows you to use what would normally be reserved keywords, like for as identifiers, should you need to.

I’m occasionally asked why it is that any identifier can be made into a verbatim identifier. Why not restrict the verbatim identifiers to the reserved and contextual keywords?
Continue reading