Holden's Blog

Address Changed

2012-02-05T11:46:00.000-05:00

As of 2012-02-12 I'll be changing the address of my blog from voigtkampff.blogspot.com to lucidswingset.blogspot.com. After that, you'll still be able to read old posts using the voigtkampff address. Nothing new will be posted to it though. Everything new will be posted to lucidswingset.

I plan on keeping voigtkampff accessible, but I do eventually want to give the name back to Blogger. So if you're a Blade Runner fan and you're looking for a place to speak your mind, let me know.

Wireless Book Management On The Sony PRS

2012-01-25T12:48:00.000-05:00

The Sony PRS is an excellent e-reader for the price. However, there was one minor thing that bothered me. Every time I wanted to read something on it, I needed to start a computer, connect the USB cable, start the management software, and finally copy over the book. Since the PRS I have has a built-in 802.11g radio it seemed like there should be a less wired, less time consuming way of getting stuff to read onto the PRS.

All of the PRS e-readers have built-in web browsers. So, exposing the files via HTTP seemed like the most probable solution. However, Sony's browser only supports downloading HTML files via HTTP GET. For example if you try downloading an epub or pdf from project gutenberg, you'll get a message about the file type not being supported. Thankfully though, the underlying operating system for the PRS is montavista linux. That means compiling additional software for it, like lynx or wget, is possible.

This is exactly what the PRS+ project has done*. Like the name suggests, it adds a number of features to the stock Sony firmware. One of the features is the ability to download files via HTTP using the built-in web browser (friendly warning, only un-authenticated HTTP currently works).

The last thing necessary was an apache webserver (any webserver with directory indexing should work though)**. Once setup, mod_autoindex will generate HTML listings for any directories configured to be indexed.

Et, voila...

* Installing PRS+ almost certainly voids the warranty on the PRS. You can potentially turn it into an expensive paper weight. If you're still willing to install PRS+, the install guide will walk you through the process.
** Web servers are probably the biggest security exploit route. if you plan on running a personal web server, consider reading up on securing it (i.e. authentication, authorization, minimal privileges, etc...).

The Importance of Algorithmic Complexity

2011-11-01T12:47:00.000-04:00

So, it's been a while since the last time I updated the blog and I figured I'd do a basic writeup just to keep it from falling into abysmal obscurity. I'm not sure how many people are following this. Still, even if nobody is reading it, I find it cathartic to do writeups from time to time.

Recently, I was faced with a problem that required less of a focus on low-level performance than an efficient algorithm. My first attempt at a solution seemed to be caught in an infinite loop. At first I thought there may be a bug, but after reading over the code I realized that the algorithm just had horrific asymptotic growth. Ultimately, I had to come up with a more efficient algorithm.

I thought it was interesting to be able to apply some of the theoretical aspects of computer science to a tangible problem. So, I figured I would talk a little about algorithm complexity, as a bit of a refresher for me, and hopefully to spark an interest an anybody who might happen to be read this.

Most of us probably remember algorithm complexity as Big O (asymptotic upper bound), with the canonical example being quicksort f(n) = O(n²) for run-time complexity. There are corresponding asymptotic lower bounds, Big Ω, and upper and lower bounds, Big Θ. Asymptotic growth can also be used to describe spatial complexity (f(n) =O(n) for in-place quicksort IIRC). However, I wanted to focus on run-time complexity since most of the problems I've seen are typically constrained by time, not space.

In order to talk about complexity, I figured I would work through one of the project euler problems. If you haven't already been to the project euler site, it's great place for finding mathematical problems that can be solved with code. Occasionally, you can solve them without it, but typically you need a computer. Most of the problems tend to be intractable via brute force, which is why I thought it would make a good example for demonstrating the effect of complexity on realized run-time.

I've been learning haskell recently, which seems to be a succinct language for solving these types of problems. So, all of the following code examples will be expressed therein. If you don't know the language, the examples should still be very intuitive, due to haskell's brevity.

The specific problem I'll be using has to do with triangle numbers.

"What is the value of the first triangle number to have over five hundred divisors?"

So, the first algorithm that comes to mind is to simply compute each of the triangle numbers, and iterate over the integers from one to the number, counting each of the divisors. The code to do this is pretty simple, and looks something like this:

It's a simple algorithm, but unfortunately it is also horribly inefficient. It should give a good starting point to developing the real solution though. Looking at the code tells us the algorithm to compute triangle number n, and determine the number of divisors it has is O(n√n), n being the triangle number. Actually, the algorithm is also Ω(n√n), which is even worse. Consider the fact we're looking for a number with over 500 divisors, and you can see how the run-time explodes. This algorithm sadly wouldn't find the correct answer even if it were given a month.

So, the obvious solution doesn't cut it. How can the algorithm be changed so the correct triangle number can be found in a reasonable amount of time? Well, at the core of the algorithm there are two algorithms, namely the algorithm to compute triangle numbers, and the algorithm to determine the number of divisors. Computing the triangle numbers is Ω(√n), and finding divisors is Ω(n). So, the asymptotic growth of one or both of those functions needs to be improved. It just so happens that there is a very simple modification that can be made to change the run-time of one of the algorithms to O(1).

The change to the algorithm computes each triangle number using a simple O(1) calculation. This calculation is a corollary of a formula, anecdotally attributed to Gauss. The formula is Σ (k) {k: 1,n} = n(n + 1) / 2, which is easily verified through induction. This is an order of magnitude better than the first iteration, but the overall algorithm is still Ω(n), which would likely take more than a few minutes to run. Surely there must be a way to further cut down asymptotic growth; Of course, there is:

The final algorithm has a run-time growth of O(√n), which I suspect is optimal for this particular problem. It takes advantage of the fact that all divisors of a number, consist of a combination of its prime factors (fundamental theorem of arithmetic). Searching for prime factors of an integer is O(√n), since no integer can consist of primes larger than its square root.

So, starting out, we only had a simple, but asymptotically horrible, Ω(n√n) algorithm that would take a tremendous amount of time to finish. However, by taking advantage of a few simple properties of integers, a simple O(√n) algorithm that finishes in a reasonable amount of time could be easily derived.

Enumerating Intel 64 Topology

2011-06-28T00:48:00.000-04:00

First, if anyone is stumbled here through facebook, let me apologize for misleading you. IA-64 is actually Intel's first 64 bit architecture, Itanium. I don't plan on running on Itanium. Having said that, if someone wants to send me the hardware, I'm sure I can figure something out :).

So, one of the projects I'm working on is a performance sensitive application. For this reason, I wanted to have a good way of understanding the inner workings of the CPU the software would be running on. Just because something fits in a single line of code, doesn't always mean it's effective or efficient. What hardware actually does with software has to be considered when the software functions in terms of milliseconds and microseconds. More importantly, how the hardware is used becomes critical. This is why I wrote a relatively simple app to give me some of the gory details about the actual system it's running against.

There are kind of a few ways of getting information about hardware you plan on running on. Hardware specifications are probably the most obvious, benchmarks are a little better, firsthand accounts are better still. However, for what I wanted to know, these things really don't tell the whole story.

I chose to take advantage of the CPUID instruction available in the x86 instruction set. CPUID is kind of a treasure trove of data. Actually, a more accurate description would be random piles of papers with random chunks of information spread across them. CPUID seems to be somewhat of a historical architecture record at least for Intel.

What I was trying to figure out was the actual topology of the logical CPUs in a system. Since different CPUs will behave with different overall latencies, and typically different cache and memory latencies, knowing this information is important.

Reading through the Intel Programmer Reference, I could only see a couple ways of accomplishing the task at hand. CPUID leaf '0x4' (cache parameters), and leaf '0xb' (extended topology). Leaf '0xb' is significantly easier to work with, but isn't available on older Intel CPUs (Intel Atom doesn't support it). I expect to be running on older and newer processors, so I ended up writing the code for both. The code to extract the info from '0xb' is trivial, and kind of not interesting. However, using '0x4' required a little insight and some clever bit twiddling.

The code's a little messy, but essentially what it does is takes adjacent topology counts, and using both of them, generate a unique id for a level . Using these id's, you can figure out precisely which siblings are closest to eachother, which CPUs potentially share L1 and/or L2 cache, so on and so on.

This kind of information is almost always used by operating system schedulers. In addition, compilers typically (hopefully) take this information into account when they generate the machine code that will actually run against the hardware. Another possible use might be highly detailed, low level benchmarks.

If anyone has any questions, please either drop it in the comments or let me know and I promise to answer it as time permits. Also, if anyone has any corrections or additions, please drop it in the comments or let me know and I'll make an update.