November 24, 2009
There’s a theorem that, although its formulation is trivial, is of paramount importance in many things, including data compression. I’m talking about the frivolous theorem of arithmetic, of course. The theorem takes many forms, but one being:
Almost all natural numbers are very, very, very large.

The converse implies that there are a lot more big numbers than there are smaller numbers. Of course, this is trivially self-evident. But this trivial theorem can serve as a brutal reality check for many hypotheses. For example, one can use the frivolous theorem of arithmetic to disprove the existence of a lossless data compression method that compresses all inputs to smaller bit strings.
Read the rest of this entry »
6 Comments |
data compression, Mathematics, theoretical computer science | Tagged: bit strings, common sense, counting argument, data compression, frivolous theorem of arithmetic, numbers, pidgeonhole principle |
Permalink
Posted by Steven Pigeon
November 17, 2009
The C (and C++) preprocessor is a powerful but dangerous tool. For sure, it helps with a number of problems, from conditional code inclusion to explicit code generation, but it has a few problems. In fact, more than a few. It is evil.

The C preprocessor (hereafter CPP) should be used with extreme care. For one thing, the CPP doesn’t know about the language it is applied on, it merely proceeds to the translation of the input using very simple rules, and this can leads to tons of hard to detect—and to fix—problems.
Read the rest of this entry »
9 Comments |
C, C99, hacks, programming | Tagged: #define, #ifdef, #undef, bug, C, C Preprocessor, C99, cpp, eviiiiiiil, eviiiil, evil, macro, operator precedence, sequence point, translation unit |
Permalink
Posted by Steven Pigeon
November 13, 2009
GnuVince just showed me the new Perl 6 logo. The butterfly Camelia:

Clearly, it looks more like a logo for some kind of association for preschoolers or for a day-care center than a logo for a programming language. It’s repulsively cute. Seeying that, I joked with GnuVince that’d I rather have a logo that felt more like the hybrid, duct-taped, patchwork Perl actually is, so I drew the hippocamptopus:

My friend systemfault took the drawing of the cussing hippocamptopus and made a O’REILLY parody of it:

*
* *
Yes, yes, I know, it’s been done before:

2 Comments |
programming, rants | Tagged: book, Bufferfly, Camelia, Cute, Cute Overload, hippocamptopus, napkin, O'REILLY, PERL |
Permalink
Posted by Steven Pigeon
November 10, 2009
Python is a programming language that I learnt somewhat recently (something like 2, 3 years ago) and that I like very much. It is simple, to the point, and has several functional-like constructs that I am already familiar with. But Python is slow compared to other programming languages. But it was unclear to me just how slow Python was compared to other languages. It just felt slow.

So I have decided to investigate by comparing the implementation of a simple, compute-bound problem, the eight queens puzzle generalized to any board dimensions. This puzzle is most easily solved using, as Dijkstra did, a depth-first backtracking program, using bitmaps to test rapidly whether or not a square is free of attack1. I implemented the same program in C++, Python, and Bash, and got help from friends for the C# and Java versions2. I then compared the resulting speeds.
Read the rest of this entry »
87 Comments |
algorithms, Artificial Intelligence, Bash (Shell), bit twiddling, C, data structures, hacks, programming, Python | Tagged: Artificial Intelligence, backtracking, bash, C, Chess, chess problem, chess puzzle, constant propagation, constant-folding, eight queens, eight queens problem, eight queens puzzle, g++, gcj, gmcs, java, puzzle, pygame, Python, python 2.6, recursion, recursive algorithm |
Permalink
Posted by Steven Pigeon
November 3, 2009
Very often, you have to keep an eye on a log, or maybe more than one log, and a couple of other things while a long-term simulation is running. The GNU/Linux distributions offer the program watch that allows the periodical execution of a command in the current interactive shell. While watch is convenient, you still have the problem of displaying the needed information in a terminal geometry aware way. Turns out, there are tools to query the terminal geometry and we can use them to write simple, effective, well displayed scripts.

So let us see how we can make BASH somewhat aware of the terminal it runs in.
Read the rest of this entry »
Leave a Comment » |
Bash (Shell), hacks, Life in the workplace, Operating System, Portable Code, programming | Tagged: cut, gnome-terminal, sed, shell, shell programming, stty, terminal, terminal characteristics, tr, xterm |
Permalink
Posted by Steven Pigeon