Your Automatisms Betray You

March 11, 2009

Yesterday someone dropped on the IRC channel where my fellow programmers, computer enthusiasts, and I hang out to get help to find a bug. He uses one of the paste sites (like pastebin.ca, pastebin.com, or rafb.net), pastes his piece of offending code, and so we get a look at the code. Of course, I go over the short program, notice a mistake in the scanf but it took me a full two minutes to notice the loop:

for (c=0; c++; c<n )
 {
   ...
 }

That kind of bug always takes a while to find because we don’t read what’s actually written, but what we think is written, unless we pay the utmost attention to the code—what we should be doing anyway, but do not always. Usually, you zero in on that kind of bug rapidly, as you guide your search from the bug’s symptoms which leads you to defect’s approximate location. If you’re like me—write a little, test a lot—you find those bugs right away most of the times. However, even if you zero in rapidly, you still get a coarse-grained location: module, class, function.

Read the rest of this entry »


Ad Hoc Compression Methods: Move To Front

March 3, 2009

In a previous post, I’ve presented an ad hoc compression method known as digram (digraph, bigram, bigraph) coding that coded pairs of symbols on used codes from the original alphabet yielding a very simple encode/decode and also sufficiently good compression (in the vicinity of 1.5:1 or so). While clearly not on par with state-of-the-art codecs such as Bzip2 or PAQ8P, this simple codec can still buy you extra space, even when using a very slow/simple processor.

This week, I’ll introduce you to another simple algorithm, Move To Front coding.

Read the rest of this entry »


Optimizing boolean expressions for speed.

August 26, 2008

Minimizing boolean expressions is of great pragmatic importance. In hardware, it is used to reduce the number of transistors in microprocessors. In software, it is used to speed up computations. If you have a complex expression you want to minimize and look up a textbook on discrete mathematics, you will usually find a list of boolean laws and identities that you are supposed to use to minimize functions.

Read the rest of this entry »


Follow

Get every new post delivered to your Inbox.

Join 66 other followers