29/06/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 »

1 Comment | algorithms, assembly language, bit twiddling, CPU Architecture, data structures, Design, hacks, Instruction Sets, Life in the workplace, Object Oriented Programming, Operating System, Portable Code, programming, theoretical computer science, Zen | Tagged: 1977, atomic, bit twiddling, branch prediction, C Standard Library, class, classes, coding, compatibility, CPU, ecosystem, global, graphical user interface, GUI, IBM, instruction, instruction set, interoperability, macroscopic, mesoscopic, methods, micro-code, micro-instruction, micro-optimization, microscopic, molecular, networking, Object Oriented Programming, Operating System, optimization, out of order execution, POD, powers of ten, premature optimization, registers, speculative execution, string, subatomic, system | Permalink

Posted by Steven Pigeon

23/06/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 »

2 Comments | algorithms, bit twiddling, C, C99, data structures, hacks, Mathematics, programming, theoretical computer science, Uncategorized | Tagged: address transformation, box plot, box-and-whiskers, boxplot, comparison sort, gettimeofday, graphs, median, microsecond, quartile, quartiles, Quick Sort, QuickSort, radix, Radix Sort, tests, timer, trials | Permalink

Posted by Steven Pigeon

16/06/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 »

2 Comments | algorithms, C99, data structures, database, Mathematics | Tagged: aces, card deck, cromulent, data mining, data set, deuces, external sorting, French suits, kings, large data set, linked lists, lists, playing cards, QuickSort, radix, Radix Sort, sorting cards | Permalink

Posted by Steven Pigeon

09/06/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 »

2 Comments | algorithms, bit twiddling, hacks, Mathematics, theoretical computer science | Tagged: /dev/random, /dev/urandom, bit recycling, Fisher-Yates, hash, md5, pseudo-random, pseudorandom, random, shuffling, urandom | Permalink

Posted by Steven Pigeon

03/06/2009
Q. Why did the multithreaded chicken cross the street?

A. To the get other to side

Leave a Comment » | programming, Zen | Tagged: chicken, multi-threaded, multi-threading, multithreaded, multithreading | Permalink

Posted by Steven Pigeon

02/06/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 »

3 Comments | bit twiddling, C, C99, embedded programming, hacks, Life in the workplace, Portable Code, programming | Tagged: C, C99, integer conversion, integer promotion, integral types, ISO/IEC 14822 | Permalink

Posted by Steven Pigeon