Generating Random Sequences (part I)

Every once in a while, we need a random sequence. Whether to test a data structure’s performance or to run probabilistic unit tests, the provided rand primitive from your favorite programming language has several limitations. First, it’s been known for a while that if most implementations of the C standard library rand() function are not very random, despite being “good enough” in great many cases. Second, and more importantly, it does not allow you to easily control the period nor to generate a permutation on , for example.

There are many methods of generating pseudo-random number sequences. Not all exhibit the same properties and, accordingly, a method may be more useful in one case and perfectly useless in another. High quality pseudo-random number generation is a notoriously hard endeavor, but there is a number of very simple algorithms that will get you out of trouble for certain specific tasks. Let us consider, for example, the example where the pseudo-random generator must generate the numbers in exactly once, in a random order, of course, in exactly draws.

The Zune Freezes: More on Unit Testing

Do you remember the epic fail that bricked the Zune a whole day on the last day of last year, a bisextile year? I described here and here how this error could have been entirely avoided using basic unit testing.

You probably remember (if you read the original post) that I first claimed that it’d take a few seconds to check all possible dates but in fact it ended up taking something like 90 minutes. This week, I come back on unit testing of a very large domain under a time constraint.

A quick Bash Fix

Remember, not too long ago I told you how to shorten path names in a Bash prompt? Well two things. Apparently, there’s a similar mechanism in Bash 4.0 with PROMPT_DIRTRIM(which I haven’t tried yet). Second, noticed that I’m frequently using many terminals opened on many machines, and I’m not always sure which is which. Using uname -n in the terminal spews the machine name, but it’d be much better if the name appeared in the terminal title bar. To do so, use the same prompt I used previously, and add $HOSTNAME (a Bash variable that holds the machine’s name) in there:

PS1='\[\033]0;$HOSTNAME: $(shorten_path "${PWD}" 50)\007\]$(shorten_path "${PWD}" 50) >'

(again, use the view plain mode if WordPress messes up the syntax again)

Short PWD in BASH Prompts

It’s not uncommon to have inordinately deep directory hierarchy on your computer, especially if you’re like me and you like to give significant names to your directory. For example, if you’re using a 80×25 terminal, the location /home/steven/download/Album Photo/2009/06 jui/20-22/21-008-St-Georges-de-la-Malbaie will cause your shell prompt to wrap around the shell window quite messily. Of course, you could show only the last directory’s name, say 21-008-St-Georges-de-la-Malbaie to continue with my previous example, but that’s a bit terse, especially if you end up on a directory whose name is unexpectedly short.

The correct solution, may be, is to arrange the prompt to show adaptively long parts of the current working directory up to a given limit, and abstract parts of the path using, say, ..., and make sure the result is legible. For example, /home/steven/download/Album Photo/2009/06 jui/20-22/21-008-St-Georges-de-la-Malbaie, using a maximum prompt length of 50 would get shortened to .../06 jui/20-22/21-008-St-Georges-de-la-Malbaie, which is already much shorter yet retained its legibility and meaning.

Filtering Noise (Part I)

If you own a car, you probably noticed that the speedometer needle’s position varies but relatively slowly, regardless of how the car actually accelerates or decelerates. Unless your speedometer is some variation on the eddy current meter, maybe the noise from the speed sensor isn’t filtered analogically but numerically by the dashboard’s computer.

Let us have a look at how this filtering could be done.

Faster than Bresenham’s Algorithm?

There’s always a number of graphics primitives you will be using in all kinds of projects. If you’re lucky, you’re working on a “real” platform that comes with a large number of graphics libraries that offer abstractions to the graphics primitives of the OS and, ultimately, to its hardware. However, it’s always good to know what’s involved in a particular graphics primitives and how to recode it yourself should you be in need to do so, either because you do not have a library to help you, or because it would contaminate your project badly to include a library only to draw, say, a line, within an image buffer.

Lines are something we do a lot. Perfectly horizontal or vertical lines have very simple algorithms. Arbitrary lines are a bit more complicated, that is, to get just right. This week, let us take a look at a few algorithms to draw lines. First, we’ll discuss a naïve algorithm using floating point. We’ll also have a look at Bresenham’s algorithm that uses only integer arithmetic. Finally, we’ll show that we can do better than Bresenham if we used fixed point arithmetic.

Checksums (part I)

I once worked in a company specializing in embedded electronics for industrial applications. In one particular project, the device communicated through a RS-422 cable to the computer and seemed to return weird data once in a while, causing unwanted behavior in the control computer whose programming did not provide for this unexpected data. So I took upon myself to test the communication channel as it seemed that the on-board software was operating properly and did not contain serious bugs. I added a check-sum to the data packet and it turned out that some packets came in indeed corrupted despite the supposedly superior electrical characteristics of the RS-422 link.

After a few days’ work, I implemented the communication protocol that could detect and repair certain errors while reverting to a request to retransmit if the data was too damaged. I then started gathering statistics on error rate, number of retransmit, etc, and the spurious behavior on the controller’s side went away. My (metaphorically) pointy-haired boss opposed the modification because “we didn’t have any of these damn transmission errors until you put your fancy code in there“. Of course, this was an epic facepalm moment. I tried to explain that the errors have always been there, except that now they’re caught and repaired. Needless to say, it ended badly.

Notwithstanding this absurd episode, I kept using check-sum to validate data whenever no other layer of the protocol took care of transmission errors. So, this week, let us discuss check-sums and other error detection algorithms.

_S for Sneaky

Ensuring that one’s costumer base remains loyal, also known as lock-in, is an important part of many software and hardware manufacturers’ business plan. Recently, I came across an especially displeasing example of sneaky and subtle customer lock-in strategy from our friends at Microsoft.

Sneaky Cat is Sneaky

Powers of Ten (so to speak)

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:

Sorting Lists (part II)

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.