Powers of Ten (so to speak)

June 29, 2009

I am not sure if you are old enough to remember the 1977 IBM movie Powers of Ten (trippy version, without narration) [also at the IMDB and wikipedia], but that’s a movie that sure put things in perspective. Thinking in terms of powers of ten helps me sort things out when I am considering a design problem. Thinking of the scale of a problem in terms of physical scale is a good way to assess its true importance for a project. Sometimes the problem is the one to solve, sometimes, it is not. It’s not because a problem is fun, enticing, or challenging, that it has to be solved optimally right away because, in the correct context, considering its true scale, it may not be as important as first thought.


Maybe comparing problems’ scales to powers of ten in the physical realm helps understanding where to put your efforts. So here are the different scales and what I think they should contain:

Read the rest of this entry »

Sorting Lists (part II)

June 23, 2009

Last week I showed you the radix sort on simple linked lists. This week, I will present a version of QuickSort modified to sort simply linked lists.

Read the rest of this entry »

Sorting Linked Lists (part I)

June 16, 2009

The sorting algorithms we were taught in class were typically simplified versions of the algorithms that assumed that the data remained in memory and in contiguous memory locations, also known as an array. What we often have, however, are linked lists. Generalizing algorithms like the QuickSort to lists is not very hard in fact if we use a modification of the basic algorithm.

For lists with numerical keys (or values), there might be a simpler algorithm that scans the list in only one direction, so that simply linked lists are a perfectly cromulent data structure, that is, the radix sort.

Read the rest of this entry »

Recycling Random Bits

June 9, 2009

It is not uncommon that for large-scale simulations you need a large volume of high-quality (pseudo)random numbers. The relatively short period of the C standard library’s rand function may make it impractical for your purpose; and you might need to resort to stronger generators such as the Linux-provided /dev/random and /dev/urandom pseudo-devices. But calling those is a relatively expensive process as /dev/random may stall until its “entropy pool” is repleted.

The /dev/urandom is the unblocked version of /dev/random, but it is also demonstrably less random. Moreover, one has to access either pseudo-devices through the file system, which in certain case introduces a noticeable impact on performance. Using other sources of randomness such as a hardware random number generator may also incur significant delays.

To avoid being stalled, I propose a simple method that will allow you to recycle bits from an expensive pseudo-random source without polling it too often.

Read the rest of this entry »

Wallpaper: Ferns

June 6, 2009

Another wallpaper. Shot in my backyard this morning.

Ferns, 1920x1200

Ferns, 1920x1200 Wallpaper

The Multithreaded Chicken

June 3, 2009

Q. Why did the multithreaded chicken cross the street?

A. To the get other to side

Safer Integer Types (part III)

June 2, 2009

A few days ago (again at the time of writing, but since I accumulate and schedule posts for a weekly release, that may already mean a few months ago) a friend was a bit nonplussed by the fact that an expression such as:

int x;
unsigned int y;

if (x+y<0)

was simply never true. At first, you’re thinking “how can this be?” because you’re trying to find values of x and y that, summed together, are obviously negative. That is, without counting on the surprising integer promotion/integral conversion system of C and C++.

Let us see what’s going on exactly.

Read the rest of this entry »