The Germans are coming (possibly)


I have already pointed out how German language books dominate in LaTeX and now I have found another area where German-language books suggest that the Germans are well-ahead of English speakers in their use of FOSS.

I can find three books on kernel virtualisation (KVM) in German:

KVM kurz & gut

KVM Best Practices: Virtualisierungslösungen für den Enterprise-Bereich

KVM: Grundlagen und Praxis kernelbasierter Virtualisierung mit Linux

(Strangely, though, none of these seems to be presently available.) In English there is only a technical report for Fedora 12 –Fedora 12 Virtualization Guide – though, admittedly, it would appear to be in print!

LaTeX and O’Reilly


the tarsier featured on the cover of Learning ...

Image via Wikipedia

I have been in touch with Anslem Lingnau, the author of the (German-language) LaTeX Hacks: Tipps und Techniken für professionellen Textsatz – and he tells me that while he would love to see an English translation of his book there seems to be no sign of one forthcoming.

Indeed a quick scan seems to suggest that O’Reilly are not so great at publishing books on LaTeX.

Anslem is also a Scottish country dancing enthusiast of note, if Dashing White Sergeants are your thing…

Fourier Series: before I begin…


Animated plot of the first five successive par...

Image via Wikipedia

Update: Graphs now fixed

Exams are coming and so I am starting to reread text books and the like in preparation. One of these is Andrew Tanenbaum‘s excellent Computer Networks.

Now, it’s not really relevant to the questions I may get asked and I am about to display some mathematical vulnerability here, but I just need to know the answers, so here we go anyway…(plus it also allows me to test out the native LaTeX support on the blog).

Tanenbaum’s book is structured as an examination of the various layers in a network stack and so begins its examination of the physical layer – starting with an examination of the impact of bandwidth and Nyquist and Shannon’s work on the fundamental limitations of any physical medium.

He starts his explanation of the impact of limited bandwidth with the concept of the Fourier series. [Fourier’s work showed that any periodic function could be represented as a superposition of other periodic, orthogonal, functions – crudely you can make any finite line by adding together lots of sine and cosine lines of different frequency and amplitude].

Now, I have obviously come across these before – both in A level maths and at university: it would be difficult to have a degree in the physical sciences without having done so! But that was a quarter of a century and more ago and I really cannot recall whether I was given a rigorous or semi-rigorous explanation or just asked to take it all on trust.

So I wanted to explain it all to myself – I don’t doubt it, clearly. Even intuitively it seems close to obvious, but I wanted to understand the maths a bit more.

Looking through various explanations I found the one on Wolfram Mathworld rather easier to grasp than the one on Wikipedia. But here’s the rub…

Wolfram states:

\int_{-\pi}^\pi \! \mathrm{sin(}mx \mathrm{)sin(}nx\mathrm{)}dx = \pi\delta_{mn}

where \delta_{mn} is Kronecker’s delta and:

\delta_{mn} = 1 when m = n and \delta_{mn} = 0 when m \neq n .

So I thought I’d try this out, and used a crude spread sheet to do it. Here is a graph of \mathrm{sin(}mx \mathrm{)sin(}nx\mathrm{)} where m = n .

sinxsiny x = y
And here it is when n = 2m

sinxsiny y = 2x
And so on … the first function would clearly integrate to something close to \pi – just assume it’s average value is 0.5 and you can see that (as the domain is -\pi to \pi ) and similarly visual inspection shows the second to be zero.

Update: Below here I start to go all wrong … see here

And in fact this seem to work well for even fractional ratios over 2 – here’s 2.5 and 9.5:

sinxsiny y = 2.5x, y = 9.5x
But this is what I get with n = 1.5m :

sinxsiny y = 1.5x
Plainly that does not integrate to 0 (nor \pi for that matter). So what have I got wrong?

Red-black trees


Example red-black tree

Image via Wikipedia

Binary trees are seen and used frequently in computing science and computing. They are a good abstraction for many naturally occurring relationships (most of our mathematics is based on binary operations, for instance) and have O(log n) complexity (ie if you went from searching a tree of 1000 elements to a tree of 100,000 elements then the search should not take 100 times longer but about 10.)

Of course that log n goodness requires the tree to be “balanced” ie for any given node there should be roughly equal numbers to the left and the right. One way of doing this is through a “red black tree” – here nodes in the tree are assigned a colour: the root is always black. The rule is that any traversal from the root to the leaves should always go through an equal number of black nodes and to ensure this is possible red nodes may be inserted in the tree, but no red node may have another red node as an immediate descendant. (A full explanation is in Introduction to Algorithms though one can also work off various explanations on the internet, though they tend to be less than complete.)

The Linux kernel natively implements a red black tree (in C) and the first bit of work I started on my MSc project was to write my own, userland, implementation so I could see processes in the same way the kernel did.

As I had got a less than glorious mark (still a pass, so that’s what counts) in the C++ exam last year I also decided that I would write this in C++ using templates. A few days after I started I discovered that actually the writers of the STL had got there before me, but as this was an academic exercise I ploughed on with my own implementation.

Essentially this is what I did on my two week summer holiday in Scotland last year! When I was there I also started (though completed when I got home) a couple of helper applications to position the tree according to Reingold and Tilford’s algorithm (which I had to translate from PASCAL) for “better drawing of trees” and a Qt application to display it all.

In fact I had a nagging problem with the Reingold-Tilford algorithm which I finally got around to fixing last night.

LaTeX to PNG representation of processes

(Interestingly the code also allows you to use the Turing-complete capabilities of LaTeX by specifying a TeX output that uses LaTeX’s own positioning algorithm – something I picked up from The LATEX Graphics Companion – that is what the example shown above uses, though unfortunately for even moderately loaded systems the LaTeX processor objects to the width of the output).

Fancy trying it? I could do with someone giving it a bash on a BSD system – not needed for my course but interesting none the less.

The code is all at GitHub memball gives the basic GraphML or TeX or plaintext output, treedraw will convert the GraphML to an SVG or serialiszed stream using Reingold and Tilford’s algorithm and treeqt will use Qt to display the tree using the serialized class. You may have to download various libraries to get it to work (certainly the libproc-dev package on Ubuntu/Debian) – I couldn’t get memball to work on a Windows machine using Cygwin but maybe even that is fixable.

There is a script in the treeqt repo to make it easier: download the sources form all three repos, build them and then run:

./setup | ./treeqt --r 1

Smaller PNG graphic files from your LaTeX


I use LaTeX (LyX as the front end) to generate the occasional bits of mathematical script that appear here. Is it bad to admit it gives me a small thrill to see how the LaTex is transformed into something mathematical – makes me feel like a proper scientist/mathematician. Well, I’ve done it now… will not display postscript natively (or if it can I have never been able to get it to work), so I usually open the .ps files in GIMP and convert them to a PNG – PNGs being optimised to handle things like line drawings and graphical images of text.

The PNGs that come out of this are of a reasonable size but they could be smaller. Some years ago I wrote some Perl code to do that (I needed something that worked in a CGI environment and while Perl is not so fast for even integer maths it was the best option).

That code is available on CPAN as Image::Pngslimmer and on a typical Linux/BSD (OSX too?) install (I am assuming you have perl and the cpan module installed) you should be able to get it on to your box with sudo cpan Image::Pngslimmer – which may ask you a lot of questions before it installs if you have never used CPAN but while YMMV the default answers should probably work.

You can write your own script or just use this quick and dirty one for PNGs of 64K or less:

#!/usr/bin/perl -w
use Image::Pngslimmer();
my $srcfile = shift;
open INF, $srcfile;
binmode INF;
read(INF, $buffer, 65535);
my $blob2 = Image::Pngslimmer::indexcolours($buffer);
my $blob3 = Image::Pngslimmer::discard_noncritical($blob2);
print Image::Pngslimmer::zlibshrink($blob3);

To use this copy the script above into your editor and save it with a name eg and then execute like this: perl some.png > smaller.png which will create a new file smaller.png from some.png (which is untouched).

The results can be reasonably impressive. This file – created by cutting from the GIMP – comes in at 14.4KB (NB the graphics you see here are preprocessed by, click on the graphics to see the original):

Proof graphic, uncompressedBut after a bit of processing with the above script, this comes in at 9.7KB:

Compressed proof graphicFinally, please do not say this doesn’t matter because your pipe is so fat. Millions of these things are being pumped through the internet every minute and the collective saving of bandwidth really would matter if we could deliver it…