Friendly Robot Overlord

Generally, suburbs that are near each other have postcodes that are in the same ballpark. Since postcodes are only 1 dimension, and locations are 2 dimensions, there are obviously going to be plenty of exceptions to the rule. But not so many that you can't make a graph like this:

So if you have two postcodes which are 10 apart (say 2000 and 2010), then on average they should be 105km apart (assuming you are working with Australian postcodes).

The graph can be drawn so it goes further in the x-direction, but things get a bit silly then:

Towards the very right, there aren't many datapoints at all (there aren't many postcodes 8000 apart) so it is actually quite accurate there, it just doens't look as cool.

I sourced my postcode data from sixfive.co.uk, processed it with python (since I'm using it at work, I figure I might as well do more with it) and plotted it with gnuplot. I also worked under the assumption that 1 degree of longitude or latitude is 111km, which I think is about right for most of Australia (though I was doing this from memory, not wikipedia). In any case, if you are using the actual numbers here for anything serious, then you are doing something wrong.

Another quick post (quick in terms of me writing this bit - not much proof reading or going out of my way to make things clear), this time with some toys to play with.

Compressor

The first is a cool compressor, which is way more general than anything I've seen. (This is talking about dynamic range compression, not compression in the file size domain like mp3).

For those not in the know, a compressor will try to increase the volume of the quieter signals, and keep the loud signals loud (hence it compresses the dynamic range). There are a couple of uses for it, one is destroying the sound of a song (see commercial radio), another is for making something sound better. This compressor should be general enough to do both.

Basically, the compressor will track the loudness of the signal passing through it, and once it goes beyond a certain threshold, it reduce the gain of the signal by some ratio. The exact time that the gain is reduced is controlled by the attack and release (in order to preserve transients, the gain reduction won't kick in straight away, and once the signal drops below the threshold it should also slowly return to the original signal).

This compressor has a very general method for tracking loudness. It takes the power mean of the samples inside a window (this gives us two parameters - the size of the window, and the type of power mean (a power mean is the generalisation of most means, so you can do an arithmetic mean, rms, or anywhere in between (or outside))). Power mean is then low pass filtered, which prevents it from jumping around lots (another parameter).

So then for every loudness, we have a response curve which maps an input value to an output value. e.g. we could have a curve that halved all the inputs, which would then halve the amplitude of the output, or we could have something that followed a square root curve, or any other curve. Since there are lots of different loudness levels, we can just specify a couple of these response curves, and assign them to loudness levels, the compressor will then interpolate between these curves to get the actual curve for a particular loudness level.

Frequency Splitter

The next toy is a frequency splitter. This takes a wave file and splits it into a bunch of new wave files each with different band pass filters applied to them. The filters aren't particularly steep edged, so you will get plenty of overlap between the output files in the frequency space. For some things this is bad, for others I can imagine it would be good. I made this as a step to make the compressor a bit more general (so it could be a multi-band compressor). Converting the compressor to being multi-band using this should be trivial, the only reason I didn't do it was because I couldn't decide what the interface would look like (that is, the code interface, not the user interface).

It just uses a whole bunch of low pass filters, and then subtracts the outputs from adjacent filters to get particular bands. Writing a simple low pass filter is super easy (output = a * input + (1 - a) * last_input) and different values of a will give you different frequency responses.

64-bit and Naming Conventions

So in the time between writing the audio library I use and now, I have changed my home coding convention (I did it at the time to ensure I wouldn't confuse work code with home code, now I don't know what the new naming convention will be as I start tomorrow). Also in that time, I moved from being a person who used x86 only to a person who uses x86, Ix86-64 and armel architectures. Some of the code in the libary was assuming 32 bits, now it should work in 32-bit, and does work in 64-bit (testing it is boring).

I also can't decide what type to use for referring to a chunk of memory that I know I'm going to access by byte. I previously used a mixture of char* and unsigned char, now I've changed to void which forces me to be really explicit in places. I'm not sure if I'll stick with this, but that is how it is now.

Download

This should compile in amkel, but there is also a make file. Although I don't like writing them, there is the big advantage that make is everywhere, so for the moment I'm going to write them... until I find/make a better solution.

compress and fsplit (C, GPL3)

There are two armies on either side of an enemy city. They can't see each other. They can only communicate by sending messengers to each other. When they send a messenger, they might get captured. If both armies attack at the same time, then they will win. If only one army attacks, then they will both lose. All of the information in this question is known to both sides. What should the General commanding each army do?

This is the Two Generals' Problem which I've rephrased slightly to make it quicker to explain, and also to introduce a loophole so you can actually get a solution. I'm not being particularly formal about this, mainly because it makes it easier for me to handwave over the details that I'm trying to handwave over, but also because it is slightly more pleasant to read.

Why it is impossible

Suppose that there is a strategy which lets them agree on the plan. Then, there must also be some sequence of events that happen which mean that they can agree by sending the fewest number of messengers. What if, the very last messenger that was sent was captured? According to our assumption, there is still an agreement so that is fine. But in that case, the strategy could be simplified by not bothering to send that last messenger. Once you do that, you have a contradiction, because we were going for the fewest number of messengers - but we just found a strategy that sends one less messenger.

Why it is possible

The correct strategy is to just attack immediately and not send any messengers. Each General should realise that sending messages will result the problem mentioned above and they will never be able to attack. But, if no messengers are sent, then the proof breaks, as there is no 'last messenger' to capture. Each General should know that the other General is infinitely smart and perfectly rational, so they can know that the other General will realise that the only way they can win is to not send any messengers.

Sneaky Tricks

So in my rephrasing, I gave the Generals a bit more knowledge - they both knew that they were making their decision at the same time. The fact that they are both making the same decision at the same time was difficult to put into the wording without making it obvious that this was the trick I was doing - I tried to do it by not mentioning time at all, and presenting all the facts in the same tense, so there is some concept of a base reference of time.

So there you have it. If you word the problem poorly enough, you can solve it.

So yes, that was quite a long break. I'm not sure if I'm back to weekly things yet, but I'm at least back to things. Someone reminded me about the two generals problem which I'd had some thoughts about, so I thought that I'd post my thoughts here, since I was planning to do so at some stage anyway.

I'm about to start a new job working for Dolby Laboratories which I'm very much looking forward to. I have two more days at my current job (which I still enjoy) and then a short break and then I'll be starting. There is no super interesting "why I'm leaving" story, nothing bad happened, it was just time to move on, and Dolby really matches my interests, so I thought it would be excellent to go there.

I didn't realise that Dolby were even in Sydney, so I have to thank jobreel for alerting me to that, with the disclaimer that I'm friends with the people behind it. On the other hand, it was the only job listing website that I used in my search, and I'd be happy with it regardless of who made it.

I'll be away for a little bit. Weekly updates therefore won't happen until they start happening again.

In the mean time, read these things:

Revealing Errors

The Universe of Discourse

Basic Instructions

Good Math, Bad Math

God Plays Dice

I think they are all pretty interesting, and probably not as well known as my other regular sites.

I tend to accumulate lots of junk in my home directory. Today seems like a good day to get rid of it. Occasionally I find a quote funny enough to save in case I need it later, other times I need to run a quick program (or see if something compiles), basically there is lots of garbage, but hopefully some of it will be amusing enough. So presenting the slightly more interesting things which I've just deleted:

Quotes

"As old hands will be well aware, it's not a new C standard without an entirely new meaning for the static keyword." - Peter Seebach

"Too many errors on one line (make fewer)" - Apple MPW C compiler

"Open letter = Can't find your email address" (I'm not sure who wrote this)

Media

An old wallpaper I used to use.

Some drum patterns (these were done in rosegarden a while ago using a different drum patch, so they sound nothing like what they sounded like originally)

Various attempts at ripping just the audio track of a dvd. Why can't someone make this easy (bonus points if each chapter gets put into its own file).

This was taken from a log file I had of a Sony AIBO running around when I was at uni.

Other

Web site and executable served by a storm worm infested computer. Just out of curiosity.

Instructions for the automatic timer I use to turn my air conditioner off at night.

Rant about whitespace dependance in programming languages and why I don't like it.

One of the files I included in my vim configuration (which I shouldn't have deleted)

Programs

A program for finding square triangular numbers (like 36 = 6 * 6 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8)

This snippet (and testing code to make sure it works in the range I needed):

int v = i;
v--;
v |= v >> 1; v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16;
v++;

(probably from Bit Twiddling Hacks)

And finally:

cat /*dev/null; echo "Happy New Year"\!
cat <<c*/ /*dev/null | cat > /dev/null
c */ () {} /*
c */ main() { cat(); printf("Happy New Year!\n"); } /*
17      format('  Happy New Year!')
         write (6,17)
         stop
         end
c This program runs in four languages with the same effect.
c The languages are C, Fortran, C Shell and Bourne Shell.
c Written by Vadim Antonov, avg@hq.demos.su
c*/

So this is something mainly for my own reference, so don't expect much interesting stuff unless you are writing a parser. But here is a tiny bit of background: When you want a computer to understand a language, you first get it to understand the words (called 'tokens') so it knows where each token starts and ends (see part 1 for slightly more on this). Once you do this, you get a list of words and you need to give them some structure so you know which adjectives relate to which nouns and that sort of thing. This is called parsing.

The obvious interesting thing in parsing is parsing mathematical equations. When you parse "1 + 2 * 3", you need to remember the order of operations, so you know that the "+" refers to the "1" and the "2 * 3", not to the "1" and the "2".

Typically, you write a description of the language in a language like in part 1:

EXPRESSION = EXPRESSION '+' MULTIPLY_EXPRESSION
           | MULTIPLY_EXPRESSION

MULTIPLY_EXPRESSION = MULTIPLY_EXPRESSION '*' PRIMARY_EXPRESSION
                    | PRIMARY_EXPRESSION

PRIMARY_EXPRESSION = number
                   | '(' EXPRESSION ')'

And then rewrite it so that it is easier for a computer to know which rule to apply:

EXPRESSION = MULTIPLY_EXPRESSION EXPRESSION_2
EXPRESSION_2 = nothing
             | '+' EXPRESSION_2

MULTIPLY_EXPRESSION = PRIMARY_EXPRESSION MULTIPLY_EXPRESSION_2
MULTIPLY_EXPRESSION_2 = nothing
                      | '*' MULTIPLY_EXPRESSION_2

PRIMARY_EXPRESSION = number
                   | '(' EXPRESSION ')'

With this form, we don't get stuck in loops trying to parse stuff. Unfortunately, if we were to parse "1 + 2 + 3", we would parse this as "1 + (2 + 3)", which doesn't seem like much of a problem with a "+" sign in there, but there is a big difference between: "(1 - 1) - 1" and "1 - (1 - 1)". So what has happened is that we have changed the associativity of the operators to being right to left.

I've always hated fixing this problem, but I found a very neat algorithm for parsing it in a top-down recursive descent parser called precedence climbing. It is a pretty simple idea in a way - instead of writing a set of functions per precedence level, write a general function and have a table of operators with their precedences and associativity, then the general function can just solve the big picture problems and you don't have to worry.

The relevant part of my parser now looks like this:

static ParseNode parse_general_expression(Tokeniser t, int precedence) {
    int num_operators = (sizeof binary_operators) / (sizeof binary_operators[0]);

    ParseNode t0 = parse_primary_expression(t);

    while (1) {
        Token op = tokeniser_current(t);

        int operator_index = -1;
        for (int i = 0; i < num_operators; i++) {
            if (binary_operators[i].type == token_get_type(op)) {
                operator_index = i;
                break;
            }
        }

        if (operator_index < 0) {
            break;
        }
        if (binary_operators[operator_index].precedence < precedence) {
            break;
        }

        tokeniser_consume(t);
        int q;
        if (binary_operators[operator_index].left_associative) {
            q = 1 + binary_operators[operator_index].precedence;
        }
        else {
            q = binary_operators[operator_index].precedence;
        }

        ParseNode t1 = parse_general_expression(t, q);

        t0 = create_parse_node_binary(PNT_BINARY_OPERATOR, op, t0, t1);
    }

    return t0;
}

But I do need to add some more magic to it, since I'm experimenting with some more whacky precedence rules: I've always thought that "1 * 2+3" should be parsed as "1 * (2+3)" since that's what it looks like, so I'm going to try to parse things that way and see if it stays sane. Typically I don't like whitespace dependence (since lots of things (like HTML) will collapse multiple consecutive spaces into 1), but it just seems so much more natural to me.

I've been getting some spam in the comments here. I haven't done anything to fix it yet, but I am actively deleting the posts. I'll think of a good solution a bit later, at the moment it is about 3 posts a day, so it isn't too bad to get rid of stuff, but soon it will annoy me enough and I'll fix it good and proper, possibly with a large change in the backend (and maybe frontend) of the site. I'd like to finish the c+ stuff first though (then I'll be able to give it a test project too).

Lots of random things today, its all a bit nerdy at the moment, I haven't been interested in much non-nerdy stuff lately.

As pointed out to me in the comments, I had a bug in the subgrep program last week. I'll explain it, but first detail how the whole thing works:

1) All of the search patterns are represented by a DFA, when you draw a DFA on paper it is a bunch of circles with arrows connecting them:

To see if a string matches a dfa, you start at a particular (fixed) node (which is usually marked, but I forgot... in this case it can be the circle marked '1'), and follow the arrow corresponding to the next letter in the string. So this DFA only works for an alphabet of "a" and "b". If when you get to the very end of the string you are at a circle marked with a double line (the '3') then the string matches. Otherwise it doesn't.

Strings that match: "b", "abaa", "aa", "bba", "baaaa".

Strings that don't: "a", "abab", "bb", "bbb", "abbbb".

2) When the computer produces the regexp, it generally makes one that is a bit inefficient, and has lots of circles which aren't needed. It turns out that for every possible regular expression, there is a minimal number of circles you need to express it, and when you have it drawn with this minimal number of circles, the structure of the thing you have drawn (that is, everything except for the label) uniquely describes that regular expression. So if two regular expressions are for the same language, then they both have the same minimal DFA. Therefore, we like to simplify the DFA so that we can tell if two regular expressions are actually telling us the same thing.

3) To simplify a regular expression, you look at each pair of circles, and check if they are equivalent. For them to be equivalent, they must both look the same (if one has a double circle and the other doesn't, then they aren't equivalent). And then you have to check if all their arrows lead to the same circles (for the same letters), if we were to look at circles "2" and "3", both of them lead to circle "3" if they read an "a", but they go to different places if you give them a "b", so they aren't the same (and "3" is a double-circle). When you find equivalent circles, you merge them together and check for more equivalent circles.

4) To check if a regular expression (P) is a subset of another (Q), you create a new regular expression called S which is the union of P and Q. The details of this won't make sense here (convert DFAs to NDFAs, create new NDFA which is union, reduce to DFA, simplify), but at the end of the process, S is another DFA (which is simplified) and you then check if it is equivalent to P, or equivalent to Q. If it is equivalent to P, then everything in Q is also in P (so it is a subset) and the same goes the other way around.

My mistake was in step 3, when I was checking if two circles were equivalent, you want to assume the circles are equivalent when doing the check. I didn't do that, so if there were two circles which both pointed only to themselves, then they should be equivalent to each other, but my program didn't notice that.

The updated source (still C code, GPL3, with makefile) fixes this (the only change is in RegExpDfa.c).

Compile and run with gcc blah.c && ./a.out:

#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]) {
    int x[2] = {618270585, 58852637};
    int i;
    for (i = 0; i < 2; i++) {
        srand(x[i]);
        while (1) {
            int c = rand() % 27;
            if (c == 0) {
                break;
            }
            putchar('a' + c - 1);
        }       
        putchar(' ');
    }
    putchar('\n');
}

In general, when someone says to compile and run some random code on the internet you should ignore them (since there are enough people out there writing dodgy code that will intentionally delete your stuff). I tell people to do it all the time, but typically it is with code where if you read it it would be obvious what it is doing. It isn't obvious what this code will actually do, but if you know a little bit of c, you can probably tell that it won't do anything bad.

When I run it on my webserver, I get this output: "zggwkrqcikhqycq kadmsdicbknhua". When I run it on my desktop I get a much more pleasant message.