Operators for Arithmetic Classes

Some time ago I was reviewing a book on numerical programming in C++. The author's had provided several value based classes for mathematical objects such as vectors and matrices. Their implementation was very poor.

They had walked into the standard trap that catches many intelligent novices by using a static data member to hold intermediate results. I commented in my review that any halfway competent C++ programmer would be able to do better.

This set me thinking as well as exploring. I was right in so far as many better implementations exist but I failed to find an efficient and unrestricted implementation of arithmetic operators for large objects.

By large I mean objects where calling a copy constructor to return a value would noticeably degrade performance.

The Problem

If you are already familiar with the problem of implementing arithmetic operators for value based objects feel free to skip this section. For the rest of you I am going to briefly highlight the difficulty.

There are a range of mathematical objects where the normal arithmetic operators (or at least some of them) would normally be used. These include complex, quaternions, vectors and matrices. There are also extensions of integers and real numbers to provide a greater range of magnitude and precision.

Many, if not most, of these involve large amounts of storage. Several involve variable amounts of storage. For the sake of simplicity I am going to consider an implementation of complex in this section. It is an arithmetic type that is well understood by most concerned with the topic of this article (See listing 1).

class Complex {
   long double real, imag;
public:
   // constructors etc.
   ?returntype? add (const Complex &) const;
   // other member functions
};

[ Those of you who are puzzled by my declaration of an add function when they expected a friend declaration of operator+() should think carefully about what they read in books. Contrary to what is commonly stated, there is no need for a global definition of operator+() to be based on friendship. Given the above member function I can write the following global function:

 inline ?returntype? operator + (const Complex & zl, const Complex z2) ( return zl.add(z2);} ]

The problem I want to address is what should ?returntype? be? If Complex objects are small enough we will be perfectly happy to substitute Complex . That is we return by value and despite any optimisations that the compiler may use the code must behave as if a copy constructor is called to create the return value as a temporary. Even in this case returning a value composed of two long doubles eats up 20 or more bytes of storage as well as possible overheads for copy construction and eventual destruction.

What we would much prefer to do is to return a Complex & (in effect a Complex * const ) because this will definitely not invoke any copy constructors and it will only take up the storage for a single pointer. So how do we do that? Let's explore a little.

First idea:

(See listing 2)

Complex & Complex::add(const Complex & z) const {
   Complex answer; // storage for result
   answer.real=real+z.real;
   answer.imag=imag+z.imag;
   return answer;
};

See the problem? Yes, it generates a hanging reference. (If you try this function with Complex as the return type, some compilers will manage to optimise the copy constructor away but you have no reason to expect this behaviour. You give optimisers a better chance if you write it:

Complex Complex::add
   (const Complex &z) const {
      return Complex
         (real+z.real,
            imag+z.imag);
}

But this mechanism is still not guaranteed to remove the copy constructor nor is it exactly appropriate for objects that include more substantial bodies of arithmetic.)

Second Idea

We need a way of providing some form of storage for the answer that will not melt away just when we need it. So the second cut comes like this: (See listing 3, over page)

Complex & Complex::add(const Complex & z) const {
   Complex * answer;
   answer=new Complex; // storage for result
   answer.real=real+z.real;
   answer.imag=imag+z.imag;
   return answer;
}

Now this is fine except that we have now virtually guaranteed a memory leak. There is no sensible mechanism for destroying the returning object when we have finished with it.

Third Idea

The first two tries either destroyed the return object too soon (at the end of the function) or too late (at the end of the program or even later). What we need is some storage that can be cleaned up or reused when we want to. The idea that many think of is to provide a static data member of the function to hold the return value. Our function now becomes: (See listing 4)

Complex & Complex::add(const Complex & z) const {
   static Complex answer; // storage for result
   answer.real=real+z.real;
   answer.imag=imag+z.imag;
   return answer;
}

This solution almost works, and actually works more often than the variation given by many authors where the static data is a member of the class rather than the function but it still fails in cases such as (for convenience I am going to use operators even though we have not strictly provided them yet):

Complex zl,z2,z3,z4,
// various initialisations etc for variables.
zl=(z2+z3)*(z3+z4 };

All attempts to patch this up fail. Actually the fact that it almost works is very bad news because we may not spot that it sometimes fails. It also leads to authors suggesting that we use the mechanism anyway but just avoid the cases where it fails. I think you will all agree that this is not a solution because it places a constraint on users that they are certain to forget.

So this is the problem, implement arithmetic classes with operators returning by reference.

A Solution

This is quite complicated so I am going to focus on the structure itself and not confuse the issue with reams of code providing a complete implementation.

I want you to consider implementing a BigInt arithmetic class with data stored in an array of unsigned char. I am going to develop it as a bundle of related classes. I hope that the reasons for doing this will become clear as we go along.

Also for simplicity I am going to avoid using nested classes because I find that mechanism often confuses the less experienced. The more experienced reader will be able to encapsulate most of the following classes inside each other.

Storage

The first thing I need is a class to provide storage space for my BigInt s. It will do virtually nothing else. (See listing 5)

Note that all the members of Storage are private. There is no public interface because the class is only a tool for higher level classes.

class Storage {
   // declare some friends
   unsigned char * c; // store absolute numerical value
   char sign;  // keep the sign bit
   int length; // how many chars needed to store value
   Storage (int n ):sign(O),length(n) {
      c=new unsigned char [n]; }
   Storage (const Storage &);
   Storage & operator = (const Storage &);
   ~Storage() {delete [] c;}
}

I will leave defining a copy constructor and assignment operator until later (actually I think you should do it as an exercise. Do not forget to handle self assignment).

Next we will move on to providing a safe but operator free implementation of BigInt . (See listing 6)

class BigInt_internals {
   Storage * value;
public:
   // constructors to create Storage objects and
   // write values to them

   void add (const BigInt_internals & second,
        BigInt_internals & answer);

   // similar declarations for subtract,
   // multiply and divide
   ~BigInt_internals() {delete value;}
}

In order to get this to work you will need to go back and make BigInt_internals a friend of Storage .

Look at the declaration of BigInt_internals::add very carefully. Note that despite being a member function to do addition it has two explicit parameters as well as the implicit parameter ( *this ). It also returns a void . In other words we are going to tell the function where it can store the answer. The following is a frame work for you to fill out to implement this function. (See listing 7)

void BigInt_internals::add(const BigInt_internals & second, BigInt_internals & answer) {
   int len=(value-lengthsecond.value-length) ? value-length+l : second.value-length+l;
   Storage temp(len);
   // provide enough storage to hold the answer
   // now write the code to actually add
   // -don't forget the sign
   answer=temp;
}

I hope your implementation of operator=() for Storage trims off leading zeros. If not you will have to go back and fix that before you write your operator=() for BigInt_internals .

Take a break. Get the above working for at least one arithmetic function (actually once you have done it for addition, subtraction is relatively simple). Use a simpler arithmetic object such as Complex if you find implementing arithmetic on objects with a variable amount of storage too much like hard work.

Once you have got the above working you will have all the functionality of an arithmetic class ready to develop an efficient implementation of the arithmetic operators.

Controlled Temporaries

What we need now is a method by which we can control the lifetime of any temporary storage we use and optimise copying away to as large an extent as we can. Time for our actual BigInt class. (See listing 8)

class BigInt {
   static * BigInt_internals link;
   BigInt_internals * item;
   BigInt (BigInt_internals &);
public:
   // appropriate constructors
   void convert(BigInt_internals &); // convert one into
        // the other but do not cleanup the linked list
   BigInt& operator = (const BigInt &);
   BigInt& operator = (const BigInt_internals &);
           // will use both convert() and cleanup()
   BigInt_internals add (BigInt &);
   BigInt_internals add (BigInt_internals &);
   void cleanup ( ) ;
   // other functions
}

The first feature of implementing BigInt is that it has a pointer to a potential linked list of BigInt_internals . Various functions will add members to this list to provide temporary storage as required. Some may take single items out of the linked list. We will need a private constructor so that member functions can efficiently create a BigInt from a BigInt_internals . This mechanism must not be available publicly because we do not want BigInt_internals arguments to be able to match BigInt parameters.

We also need a cleanup() function that will dismember our linked list at moments of our choice. One such moment will occur when we assign a BigInt_internals to a BigInt . At this stage we can safely cleanup our stack because we will have completed a self contained evaluation of an expression and captured its result in suitable storage.

Note that we have two versions of assignment. One will copy the value of the BigInt argument to the BigInt on the left (remembering to dispose of the previous value first, and checking for self assignment). The other must remove the BigInt_internals from the linked list, delete the current value from the BigInt on the left, reset the pointer to the value on the right and finally call cleanup() to remove the linked list (usually already empty).

There are also two versions of each arithmetic function. One takes a BigInt and the other takes a BigInt_internals (the result of some intermediate function). When you implement these with calls to BigInt_internals::add() you will:

In the case of the version taking a BigInt parameter you will need to add a new BigInt_internals to the linked list and pass it to the answer explicit parameter for the answer.

In the case of the version taking a BigInt_internals argument you can reuse that for the answer. Look carefully at the skeleton for BigInt_internals::add() and note that the return value is only moved to the answer parameter after the calculation was complete.

Now we are ready to provide the global operators for BigInt s. There are four for each operator: (See listing 9)

BigInt_internals& operator + (const BigInt& i,
                                    const BigInt& j)
{
   return i.add(j);
}
BigInt_internals& operator + (const BigInt& i, const
                                    BigInt_internals& j)
{
   return i.add(j);
}
BigInt_internals& operator + (const BigInt_internals& i,
                                    const BigInt& j)
{
   return j.add(i);
}
BigInt_internals& operator + (const BigInt_internals& i,
                                    const BigInt_internals& j)
{
   BigInt temp;
   temp.convert(i);
   return temp.add(j);
}

Notice that in this last version we cannot use an assignment because this is one case where we do not want to cleanup() the linked list.

In practice you will probably want to inline most or all of the functions providing the operator overloads.

Important Notes

You must not provide any form of implicit conversion between BigInt and BigInt_internals because that would endanger the protection built in to handle cases like:

void fn(BigInt &);

This function is not aware of cleanup() but it does not have to be because the result of any evaluation of an expression involving operators will be a BigInt_internals which will not match the parameter. The writer of fn() can provide a second version that does a cleanup if it seems appropriate but until such is provided attempts to call fn() with a BigInt_internals will generate a compile time error.

The user of fn() can also handle the problem explicitly by using the convert() function and explicitly calling cleanup later if it is necessary (it will normally be called implicitly at some stage).

Great care needs to be taken when client programmers use BigInt_internals because they can implicitly call for a cleanup at too early a stage. If this is too dangerous in your environment the problem can be fixed by making convert and cleanup private functions though this will require some global functions to become friends of BigInt .

It is also possible to place further restrictions by making BigInt_internals a private local class of BigInt , but at that stage you will have to start declaring friendship to reams of global operator overloads.

Conclusion

The purpose of this article has been to demonstrate that it is possible to handle arithmetic operators efficiently with objects where return by value is inappropriate.

Those who know me realise that I have a continually problem with lack of time. I would love to be able to provide fully tested implementations of this mechanism for classes such as matrices but I know that I will not have the time to do so. I hope that one of you will find the time to expand this material into one or more libraries. I hope that you will make such libraries generally available.

And one final thought (and I do not know the answer), is a one-by-one matrix a simple number (int, float or whatever)? The answer matters because of the rules for matrix multiplication. I suspect the answer is no.

Francis Glassborow