More Blinking Lights (and a disgression)

28/04/2009

In Blinking Lights I told you about how I feel the modern computer for its exterior, except for its screen, is boring. When I look at my Antec case, I see a large, silent black box, which, by its very definition, is uninteresting at best. Something like a rock that slowly dissipates heat.

However Bill Buzbee built a computer that has an interesting exterior, and a much more interesting interior: the Magic-1. The Magic-1 is a computer running at 4.something MHz, and is in the same computational power range as the original 8086 4.77 Mhz IBM PC, except with a more advanced instruction set.

The Magic-1 Computer

The Magic-1 Computer

Read the rest of this entry »


Different problems aren’t always different

21/04/2009

Magic Squares are much less frequent than latin squares in computer science (on which we may come back in the future), but they have a number of (fun) applications.

Historically, magic squares are tied to numerology, alchemy and other esoteric sytems. However, as you may already know, I’m not interested in pseudoscience except to debunk it, so this post isn’t about using magic squares turtles to predict the level of the river running behind your house.

Albrech Dürer's Melancholia I

Albrech Dürer's Melancholia I

Read the rest of this entry »


Ad Hoc Compression Methods: RLE (part II)

15/04/2009

Yestermorning I presented an ad hoc compression method known as RLE, or run-length encoding and I got quite more reactions than I thought I would. Many suggested doing plenty of other stuff despite the fact that the post was about RLE, not about <insert your favorite compression method>. But something very nice happened: people got interested and many suggestions came forth.

I decided to implement the median-based prediction method as suggested by Dark Shikari here. Let us see the results!

Read the rest of this entry »


Ad Hoc Compression Methods: RLE

14/04/2009

Suppose you have been sub-contracted by a video game company, say Nintendo, to come up with an low power, low-memory, implementation of a popular video game, say, an installment of the infamous Pokémon series. The envisaged device is very slow (it has a 2MHz processor) but has a 220×176 pixels color screen capable of displaying 32768 different colors. It also has a hardware sprite mode, but sprites are limited to 4 distinct colors. You have to encode the complete database of Pokémons, which are several hundreds, in as little space as possible. Each image vary somewhat in size, but can only have 4 distinct colors from the possible palette of 32768 colors.

A typical Pokémon would look like:

A typical Pokémon image, shown enlarged and in original size.

A typical Pokémon image, shown enlarged and in original size.


Since the artists put a lot of efforts into drawing the critters in 4 colors, and because of the hardware requirements, you cannot use a compression algorithm that modifies or creates more colors than the original image had, therefore excluding JPEG. Moreover, the JPEG codec would be too complex to port to the platform considered. You must therefore use a simple lossless codec.

We will be comparing 5 codecs for the Pokémon image database. We will be looking at a “block” codec, which will serve as a comparison for a non-RLE codec. We will be looking at 5 variations on the theme of run length encoding, or RLE, namely, the All Counts, the Bit Select, and Auto-Trigger RLE. The last variant will help Auto-Trigger RLE by using predictors, transforming the input image into one that is easier to compress using RLE.

Read the rest of this entry »


Compact Tree Storage

07/04/2009

Implementing data structures in a way that uses efficiently memory should always be on your mind. I do not mean going overboard and micro-optimizing memory allocation right down to the bit. I mean organize data structures in memory so that you can avoid pointers, so that you can use contiguous memory segments, etc. Normally, minimizing storage by avoiding extra pointers when possible will benefit your program in at least two ways.

First, the reduced memory requirement will make your data structure fit in cache more easily. Remember that if pointers are 4 bytes long in 32 bits programming, they are 8 bytes long in 64 bits environments. This yields better run time performance because you maximize your chances of having the data you need in cache.

Second, contiguous memory layouts also allow for efficient scans of data structures. For example, if you have a classical binary tree, implemented using nodes having each two pointers, you will have to use a tree traversal algorithm, possibly recursive, to enumerate the tree’s content. If you don’t really care about the order in which the nodes are visited, what’s quite cumbersome.

It turns out that for special classes of trees, complete trees, there is a contiguous, and quite simple, layout.

Read the rest of this entry »


Suggested Reading: The Race for a New Game Machine

04/04/2009

David Shippy, Mickie Phipps — The Race for a New Game Machine — Citadel Press, 2009, 256 pp. ISBN 978-080653101-4

(buy at Amazon.com)

(buy at Amazon.com)

This book, strongly reminescent of Tracy Kidder’s Pulitzer-winning Soul of a New Machine, relates the history of the development of the Cell, Xenon, and Broadway processors, the hearts of Sony’s PS3, Microsoft’s Xbox 360, and Nintendo’s Wii game machines, respectively.

Read the rest of this entry »


Back from Nashville

04/04/2009

I am just back from the IEEE Symposium Series on Computational Intelligence 2009 in Nashville, Tennessee. That was quite an adventurous trip (complete with tornado alerts and all) but more importantly, I got to present a paper accepted at the CIMSVP conference (see here for the paper).