Unknown Programmer’s Blog

If we want to be better programmers we must, among other things, try to learn new things and train in those that we already know, as often as possible. Training without an objective can bore really soon, and to help us on that there are some public web pages out there offering simple, and not so simple challenges. I want to tell you today about ProjectEuler.net:

Project Euler homepage

Project Euler offers you an extensive (242 at the moment, and growing) collection of short mathematical problems, and it asks for a numeric answer to them. There are some easy problems and others that aren’t trivial at all. As you can see how many people have solved each of them, you can guess its difficulty.

As you aren’t required for the code but only for the solution, you can code your solution program in whatever language you want, even in script programs of mathematical suits like Mathematica or Maple. Another good thing about Project Euler is that, once you have solved a problem, you can comment the rest of people who has solved it about what you have done to reach the solution, and there is a pretty active community, and a variety of solutions for every problem are exposed.

I started solving some of them in C++ and then stop solving more problems, until I found a post by Louis Brandy commenting how well Python fitted the needs that that challenges require, and as I knew something of Python but had it a bit rusty, I used those problems to improve my skills in this pleasant language to program in.

I encourage you to give it a try, as it can help you improving both mathematical, algorithmic and (new) language skills. I think that I’m going to try to solve some of them with a non-imperative language, a field where I don’t have many experience at the moment.

Training algorithm, improving, language, Training

It may seem a bit useless talking about some sorting algorithm at this point in computer history, and specially about one that dates back as far as 1887. Some people consider that it is enough to know what the sorting routine in your language/library of choice is, but I consider that:

• It’s definitely good to have a breadth knowledge about different topics in Computer Science, and sorting is a basic field in algorithmics.
• Radix sort is not useful sometimes, but it can give you a performance boost in some other circumstances.
• It may seem that all programmers already know how this works. I am sure that not only most of them don’t know how it works, but that there are many Computer Scientists that don’t even know of its existence. I myself did not realize of its existence until I have spent almost all of my years at university.

So, what is radix sort about? It’s not like the basic and traditional sorting algorithms in the sense that no comparisons are made during its execution. Thanks to that, it can break the theoretical O(n log n) lower limit of a sorting algorithm. It’s time complexity is O(k*N), which makes it lineal. (k, in our implementation, will be the number of bytes of the elements to sort).

Let’s go to the point. Imagine first that we want to sort some bytes, for example:

5, 44, 200, 110 and 90

We have a first buffer of 256 integers that will act as a counter of how many bytes with that value are there to sort. We will call this the distribution buffer, because it stores how the bytes are distributed. In our case, all would be set to 0 except elements 5, 44, 90, 110 and 200 which would be set to 1. So, we traverse all the input elements incrementing the counters:

// source is an array with N elements to be sorted
unsigned int distribution[256];
for(unsigned int i=0; i < 256; i++)
	distribution[i] = 0;

for(unsigned int i=0; i < N; i++)
	distribution[source[i]]++;

Once we know how many elements of each value are there, we use another buffer of 256 entries too, which we will call indices buffer, to accumulate the values from the distribution buffer. The entries at the indices buffer indicate at which position, once sorted, an element with a certain value must go. Here, elements until 5 would be 0, elements from, 6 to 44 would be 1, from 45 to 90 would be 2, and so on.

unsigned int indices[256];
for(unsigned int i=0; i<256; i++)
	indices[i] = 0;

for(unsigned int i=1; i<256; i++)
	indices[i] = indices[i-1]+distribution[i-1];

Finally, we iterate over the input elements again, and as we know at which position do they correspond when sorted, we can put them at their place in a new buffer called destination buffer, and which has the size of the input buffer. Once did this, we increment the index for that value as the next element with the same value (if there is another) must go not to the same entry but to the next one. If we want the sorted values to go in the source list, we copy them.

unsigned char destination[N];
for(unsigned int i=0; i < N; i++)
	destination[ indices[source[i]]++ ] = source[i];

for(unsigned int i=0; i < N; i++)
	source[i] = destination[i];

Well, you may say now, I do not want to sort only bytes, I want to sort, for example, 32 bits integers, and if I have to create a couple of buffers of 2³² elements each this algorithm is not going to be very useful. That's right, but you don't have to do that. You can notice that due to the way the elements are iterated again looking for its corresponding sorted index, and then that index being incremented, this sort is stable (In short, a stable sort is one which, for elements with the same sorting value, the output order is the same as the input).

So, as the the algorithm is stable we can sort larger types without the need of larger distribution and indices buffers. All what we are going to do is sort first taking into account only the least significant byte, then sorting by the next more significant byte, until we have sorted the elements by the most significant byte, at which point the elements are completely sorted.

In fact, and by what we have seem, it may seem that only unsigned integers can be sorted by radix. But negative and even floating point numbers can be sorted with radix sort, as exposed by Pierre Terdiman.

If you are interested in the topic, more tricks and optimization techniques can be found in this article by Michael Herf.

Algorithms, Optimization algorithm, Optimization, radix, sorting

There’s basically only one way unsigned integers are represented with bits: in binary, namely, a sum where each bit represents a power of 2, from 2^0=1 being the least significant bit (the rightmost bit) to 2^(n-1), the most significant or leftmost bit. The represented number is the addition of those powers whose bit is set to 1.

But things are not as easy as that when trying to represent also negative values.

Sign and magnitude

This is probably the easiest way to understand, for a human, of solving the problem. The approach works basically setting a bit, usually the most significant one, to represent the sign. A 0 on that bit means that it’s a positive number and a 1 means that it’s a negative number. All the other bits represent the magnitude or the absolute value.

Unfortunately, this system has the disadvantage of having 2 ways of representing 0 (100…000 and 000…000) and that hardware built to operate with it requires special logic to handle signs.

Excess-N

This one is another easy approach to the problem. It consists in setting an offset to every number represented by it of the minimum number you want to be representable, usually -(2^(n-1)). Thus, all bits set to 0 is the minimum representable value and 0 would be represented by a 1 in the most significant bit and 0 in all the other bits (100…000).

This is not used currently in signed integer representation but it’s used in the exponent representation of floating point numbers (more on that topic in another post).

One’s complement

Another representation is that known as “one’s complement”. To negate a number, you just have to apply the bitwise operation “not” to it. Positive numbers are those starting by 0 and negative numbers those starting by 1.

With this system we still have 2 ways of representing 0. It helps on addition because you don’t have to worry about the sign of the operands, and subtraction is very simple too as all you have to do is negate the second operand and do an addition. So, addition and subtraction are easier in one’s complement than in sign and magnitude, but multiplication is not easy enough, as you must take care of the signs.

Two’s complement

Two’s complement came to solve the problems with the other representations. There is just one way of representing 0 in it (all bits set to zero) and there aren’t the operating problems that there were with one’s complement.

To negate a number in two’s complement all you have to do is negate it bitwise and add 1. A great thing about two’s complement is that numbers represented in this way can be added, subtracted and multiplied without taking care of the operands’ signs.

It’s important to note that when expanding a number in two’s complement, new bits at the left must be the same as the previous most significant bit in order to preserve the value of the number. This is known as sign extension.

With the advantages we have just seen is no surprise that this is the representation used in most systems currently, so this is the system to know, if you are a programmer you should know how it works perfectly. Not only the basics exposed here but more deeply. Knowing how it works is essential to some things as bit hacks, which will be covered in some post to come.

To learn more: Two’s complement in the Wikipedia

Architecture Architecture, bit hacks, introduction, representation, two's complement

Let’s face it: we’re not all the best programmer in Earth.

And let’s say more: we’re not all above the median. Only half of us is. That means that half of us is below the median as programmers.

All of us (at least those of you reading a programming blog) want to improve as programmers. The first thing to do to improve is to be aware that you have to improve. This can seem obvious, but as the Dunning-Kruger effect states

“ignorance more frequently begets confidence than does knowledge”

competent people is usually more aware of their lack of knowledge areas than incompetent people.

The second thing is to know is where do you have to improve, which are your best skills and which ones you should train more. This, of course, depends greatly in the specific area of programming you are interested in and in your objectives and priorities.

Taking that into account, I have found a resource that has been helpful to me and that I think that can be helpful to many of you too. It’s the Programmers Competency Matrix. It’s not completely exhaustive and doesn’t includes some specific areas, as well as some points are a bit ambiguous and others require being very honest about oneself, but it can guide you to know what to improve, as well as knowing other programmers’ level.

Remember that in the long term is not as important how much do you know as how fast do you learn new things. So, I hope that you find it interesting and useful in order of being a better and more balanced programmer.

General improving

The term “wheel of reincarnation” was first coined in a paper by T.H. Myer and I.E. Sutherland named “On the Design of Display Processors”, and refers to the cycle, completed many times in computer history, of migrating some kind of work to special designed hardware in order to gain speed and liberating the CPU for other tasks, then this hardware becoming of more and more general purpose and powerful, and finally integrating it again into the CPU to simplify the architecture.

Let’s have now a brief look at 3d graphic cards history.

The first 3D graphic cards started in the early and mid-90’s and were only rasterizers, leaving all other tasks in the CPU. Later, in the late-90’s, the Transform and Lighting stage went to the graphic card too, allowing for greater detail scenes and to do more work on the CPU.

In the early-2000’s, they did a great step towards generalization, with the appearance of shaders (small programs executed for every vertex, every fragment or , more recently, for every primitive to be rendered). Shaders had to be very simple at first, with a very limited number of instructions, with lack of branching and other limitations, but over the years those limitations have been relaxing or disappearing.

The graphic cards, at that point already named “GPUs”, were specialized in the processing of floating point numbers, and so programmers solving numeric problems of this kind started to use them, and GPGPU (General Purpose Computing on Graphical Processing Units) was an expanding field.

As more kind of programmers were attracted to use GPUs to solve their problems, so were GPU companies to offer them more attractive technologies, and special languages to allow generic computations on the GPU started to appear, such as NVidia’s CUDA or OpenCL.

Now, with Intel’s GPU project, Larrabee, which is based in x86 processors, the difference between the CPU and hardware processing graphics will be reduced again, and the wheel of reincarnation in the graphic cards field is one step nearer to be completed.

Will it be finally closed? I think so. When? We will probably have to wait many years before getting enough powerful CPU as to host the usual computations of high-demanding applications such as last generation games and at the same time process their graphics rendering, which will be for sure way more advanced and complex than what it is currently.

Architecture, General, Graphics Architecture, cuda, future, graphic cards, Graphics, history, larrabee, opencl