# Operators for Arithmetic Classes

Operators for Arithmetic Classes

By Francis Glassborow

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 };`````` Listing 1 - Class ``` complex ```

[ 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; };`````` Listing 2 - A first idea

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; }`````` Listing 3 - A second attempt

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; }`````` Listing 4 - Adding a static

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;} }`````` Listing 5 - The ``` Storage ``` class

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;} }`````` Listing 6 - A start on class Big

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; }`````` Listing 7 - Framework for ``` add() ```

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 }`````` Listing 8 - The Actual ``` BigInt ``` class

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); }`````` Listing 9 - Global operators

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