Vectors-the last word - Embedded.com

Vectors–the last word

Engineers and mathematicians have been encountering the zero vector for as long as vectors themselves have existed. Here's how to handle it when writing a computer program.

When I uploaded the code for my last column, I included all the vector functions in class Vector, but I didn't discuss them all. My first order of business this time is to cover those functions we haven't discussed yet.

The key function is the function Norm( ) , which computes the scalar length of a vector. For a vector of length N , the norm is defined to be:

(1)

(Here I'm using the mathematical index convention, where the first element is element 1.) The norm of a vector is the same as its absolute value, often written:

A related function, Unitize( ) , takes a vector of any length and returns one whose norm is equal to 1. This kind of vector is called, unsurprisingly, a unit vector , and a need for such a vector pops up quite often. The unit vector has the definition:

(2)

This usually works. Unfortunately, it doesn't, always, and I'm sure you can see why. If every element of r is identically zero, so will be its norm. The operation will fail, and fail catastrophically, with a divide-by-zero exception.

Engineers and mathematicians have been encountering this problem for as long as vectors themselves have existed. When you're doing analysis by hand, it's easy enough to recognize the situation and deal with it as a special case. But if you're doing it in a computer program, you absolutely must tell the computer what you expect it to do in the exceptional case. In real-time software, a crash and burn response is not an option.

The na├»ve approach is to simply implement Equation 2 verbatim and hope for the best. After all (one might argue), how likely is it that we will actually encounter a truly zero-length vector, in practice? Answer: very likely indeed, if that's the value the vector is initialized to (that is, in our default constructor). A friend of mine was once given the task of modifying some existing code–a production-quality product that had been running and heavily used for years. No one had ever encountered a problem. It constructed a unit vector based on the difference of two other vectors. For his test case, he chose the simplest one he could think of, which was to use the same vector in the difference operation. That gave him a zero vector, and you know the rest.

In real-time software, we must test for the norm before we divide, and do something special for that case.

But what should the special thing be? Some folks choose to return a zero vector for the exception null case, but that choice presents its own problems.

When you use a library function, the description of the function represents some kind of contract between ths software and the user. Give the software an input meeting certain criteria A , and it will (and had better) return results meeting criteria B . In the case of Unitize( ) , the user has every reason to expect that the vector returned will have a norm of 1. Returning something else constitutes a breach of contract.

The problem in this case is not that we can't return a unit vector; that there is no unit vector parallel to the input vector. The problem is that any unit vector is parallel to a vector 0. So, which one should we return?

After dealing with this problem for decades, it finally dawned on me: since any unit vector is satisfactory, let's just pick one. In the exceptional case, I return:

(3)

which is as good a choice as any other.

Where possible, I've included multiple versions of the operators. I have a member function Norm( ) , which returns the scalar norm of *this . You call it by writing:

    s = a.Norm( );   

A second version is a friend function that takes an argument of type vector:

    s = Norm(a);   

Similarly, there are two versions of Unitize( ) and two versions of the in-place negation operator. Because the functions are so tiny, there is not much to be gained by keeping the class austere. In the case of negation, the friend function is the overloaded, unary minus operator, called as in:

    b = -a;   

The last set of functions are those used in comparisons. I've included the full set of six functions, which are == , != , < , > , <= , and >= .

The test for equality (and inequality) is special. We declare two vectors to be equal if and only if they have the same length and the same element values, element by element. Likewise, two vectors are unequal if any two elements differ, even though they may have the same dimensions and the same norms.

For the remaining comparison tests, the only reasonable test is on the norms. The vector x is said to be greater than y if norm(x) > norm(y) .

The new default constructor
Now for the change that I hinted at in my last column, and which I'm pretty excited about. This change affects the way the default constructor works.

For the most part, I've been very pleased with the way the vector class worked out. Most of its structure and its functions are nice and easy to use, and work very well. I've not been nearly so enamored of the function Init( ) , and the need to use it.

The problem lies in knowing the size–that is, the number of elements–of the vector to be constructed. Most of the constructors have no problem with this; the copy constructor and the converting constructors get their size information from the data passed to them. It's only the default constructor that doesn't know what size vector it's expected to create.

Every class needs a default constructor; the compiler insists on it. If it has to create a temporary object of the class, it needs some constructor to call. If we don't explicitly define a default constructor, the compiler will create one, but we probably won't like what it creates.

At one point, I thought I had a clever solution in the use of a default parameter. By definition, a default constructor is one that requires no arguments. But the “default” constructor can have as many arguments as we like, as long as they all have default values. I thought that, by using a default size, as in:

    Vector(size_t n = 3);   

I'd give the compiler a default constructor it can call. And indeed, it will, but we're not likely to like that result, either.

Consider what happens when I want to create an array of vectors. I can declare:

    Vector vArray[4][5];   

and the compiler will dutifully create such an array–of vectors of size 3. It will create storage for an array of 20 vectors and call the default constructor for each of them. Since it can't and won't pass any parameter to the default constructor, each vector will end up constructed with a size of three.

This might be what we want, but it might not. What I'd really like to do is to be able to tell the compiler what size vector I want, when I declare it. I'd like to be able to say something like:

    Vector M[4][ 5](7);   

where the 7 is a size parameter. But this construct simply doesn't exist in C++. That leaves me with two options, neither of them very pleasant. I can let the compiler go ahead and allocate the vector using the default size, 3. Then, after it's done so, I can go in and resize each vector, one by one. I'll have to provide some function–call it Resize( ) –that can do the task. But that option is not very attractive, because it involves allocating, then deallocating, then reallocating the storage for each vector, in each array.

The other alternative is to let the default constructor construct null vectors and then provide a function Init() to actually allocate storage of the size I want. I'll have to call a function for every vector in the array, either way, but at least I'll only be allocating the storage once.

I chose the second option, and that's the one you've seen in all my listings. But just as I was wrapping up my last column, I thought of an even better way to deal with the problem. What's more, the new approach is simple and clean and requires only minimal changes to what we have already. I'm embarrassed that I didn't think of it sooner.

The trick is to be able to tell the class's default constructor what size vector to construct, without having to pass it a parameter. We can do that by using a class variable. Such a variable “belongs” to the class, rather than to a given individual object, and is available to every function in the class, including the default constructor.

You create a class variable using the static keyword. In our case, the class definition becomes:

class Vector{    size_t sz;    double *p;    static size_t vecClassSize;public:    ...}   

All vectors share that single, global copy of the variable vecClassSize.

The new default constructor now knows what size vector it's supposed to create, so it's much more straightforward than before. Here it is:

Vector::Vector(void){    assert(vecClassSize >0);    sz = vecClassSize;     p = new double[sz];    vClear(p, sz);}   

The call to vClear( ) is not necessary, but it's a good idea to clean up the contents of the array before using it.

Now, initializers are not allowed inside class definitions, so we can't use an initializer to give the class parameter a value. Instead, it must be initialized explicitly, somewhere in the main program. It must be done outside any function, including main( ) . The declaration should be something like:

    size_t Vector::vecClassSize = 3;   

All the parts–the type and the explicit reference to the class–are necessary.

For my final trick, I'll write a couple of functions to let me change the class variable:

    friend size_t GetVectorSize(void);    friend void SetVectorSize(size_t vsz);   

The functions themselves are one-liners. Now I can create that array of 7-vectors in the cleanest kind of way:

    SetVectorSize(7);Vector M[4][5];   

No fuss, no muss. The only restriction is that all the vectors in the array must have the same size. But that's not a restriction that's likely to bind us at all. If you really, really want an array of vectors in which each of them can have a different size, you're probably better off not using this class at all. The STL class vector might be a better choice.

Of course, if you change the default vector size as I've done above, you may have to change it again for the next usage, but that's not much of a restriction, in practice. Remember, the default constructor will only be called for occasions like this, where the compiler needs to create new objects without using passed parameters. The copy constructor and converting constructors get their size information from their arguments, and they don't use the class variable at all.

When vectors meet matrices
The vector class is now complete. You'll find the code for it at http://www.eetimes.com/design/embedded/source-code/4200228/SimpleVec as usual. I hope you find it useful.

As handy as it is to be able to manipulate vectors, it becomes far more so when we can use vectors and matrices together. The class Vector cries out for a class Matrix, and that's what we'll start developing next time. See you then.

Jack Crenshaw is a senior systems engineer at General Dynamics and the author of Math Toolkit for Real-Time Programming. He holds a PhD in physics from Auburn University. E-mail him at jcrens@earthlink.net. For more information about Jack click here

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.