Ugh. I've always hated the word 'blog'. In any case, this is a chronologically ordered selection of my ramblings.

Special relativity, part 2

Warning: I'm so depressingly out of practice at mathematical things that I could well have stupid mistakes in the following. Sorry! If you spot anything wrong, please mail and correct me...

Some more notes on special relativity as I traverse Taylor and Wheeler's Spacetime physics.

Subjective travel times

So, I like hyperbolic rotation stuff, because it makes addition of change of velocity behave in a nice additive fashion. We have the relativistic velocity as tanh(zeta), where zeta is the rapidity. I like rapidity because it's additive and at low speeds is the same as velocity. From the point of view of a person accelerating to a relativistic speed, they can treat the acceleration as a large number of small changes of velocity, and the rapidity is the velocity they would expect to have in a Newtonian universe.

In a Newtonian universe, travelling distance d would take time d / zeta. Subjectively, in a relativistic universe, things would move past you at velocity v = tanh(zeta). On the other hand, Lorentz contraction would make the distance d' = d / cosh(zeta). Subjectively it would take time d' / v = d / (cosh(zeta) * tanh(zeta)) = d / sinh(zeta) < d / zeta.

In other words, if you're going somewhere far away, subjectively it takes less time than in a Newtonian universe!

Interpretation of interval

The interval, t^2 - x^2, is a nice invariant, but what's its physical interpretation? The "straight line path" is the route that maximises the interval, and (for time-like paths) you can find a frame in which the x movement is 0 zero, in which case the interval is just the square of the most time you can experience going between the points in space-time. Which is also known as proper time.

About this point, I realise this is all covered about 4 pages ahead of where I got to in Spacetime Physics.

Change of velocity as shear

In Newtonian mechanics, a change of space or time reference point is a translation, and a change of velocity is a shear. In special relativity in its normal representation, a change of reference point is a translation, but change of velocity is nothing like a shear. Can we find a way of reformulating things so that it is a shear, at the cost of making a change of reference point into something quite different?

Yes we can! First of all, we make the y-axis into sqrt(t^2 - x^2). As each line of constant y now represents a particular interval, the y-axis value is unmodified by a change of velocity, as required for a shear. By using a square root, the y-axis is still a time axis for x = 0.

Then we want the x-axis to behave like a shear during change of velocity, with it being affected by a translation, proportional to the distance up the y-axis. A thing that behaves additively under change of velocity is rapidity, and moreover each point along the x-axis for a fixed value of the y-axis (interval) represents a specific rapidity required to reach that point in spacetime. So, if we change the x-axis to sinh^-1(x), we get the behaviour we want!

Admittedly the resulting representation of spacetime doesn't behave nicely under translation or have other properties we'd like, but still!

Uniform acceleration doesn't lead to uniform time

One of the things I found fairly unexpected is that, given two identically accelerated objects, positioned at different points in the direction of acceleration, they will age differently. This carries through to general relativity, so that objects in a uniform gravitational field age differently. In other words, you can tell that you're undergoing uniform acceleration, and it's not equivalent to genuine free-float, which I find utterly unexpected.

Time in the rest frame as action points

As I have little intuition about the Lorentz metric, I've been playing around in order to get a feel for it. This motivated the "relativistic change of velocity as shear" thing above. It's very tempting to try to reframe the Lorentzian metric as a normal Euclidean one. So, one way to look at it is to track the motion of a set of particles in a particular reference frame. Each particle, in this reference frame, can move some distance x and accumulate some proper time sqrt(t^2 - x^2), for a given amount of time in the reference frame, t.

In other words, a particle, measured against a reference frame, can "choose" to spend that reference frame time on moving or experiencing the passage of time. In the parlance of turn-based strategy games, time in the reference frame is actions points that can be spent on movement (in the reference frame) or action (subjective experience of the passage of time), albeit with a Euclidean l2 norm, rather than the l1 norm of those games (sum up movements plus actions).

Put another way, reference frame time is path length of a path representing travel through a Euclidean metric spacetime of reference frame space and subjective time. This does not look particularly helpful, since you are unlikely to want to match subjective times together, but I thought it a nicely different way to look at things.

Posted 2015-12-20.

Special relativity, part 1

Warning: I'm so depressingly out of practice at mathematical things that I could well have stupid mistakes in the following. Sorry! If you spot anything wrong, please mail and correct me...

So, I'm slowly working through Taylor and Wheeler's Spacetime Physics, which is a reasonable pile of fun. I reached the halfway point during my gardening leave, and have basically been on hold while I've been learning the new job. However, I thought it worth starting to write up some notes on the things I've been thinking about while learning special relativity.

  • Invariance of interval is a great starting point for the book. I'd previously read explanations based on Lorentz transformation, and this is a much more intuitive explanation.
  • Change of reference frame The fundamental point is that a change of reference frame that changes velocity is no longer a shear, but a hyperbolic rotation. Talk of hyperbolic functions was in the first edition of the book (which I "trialed" before I bought the paper copy), but sadly taken out of the second edition.
  • Lorentz contraction is weird If we go past each other at speed, you seem shorter, with time going slower to me, and you see me as shorter with time going slower? Yep. This is not entirely alien - you get the same thing in a non-relativistic world where, if we run past each other while making a noise, we both hear the same Doppler effect coming from the other person. It does seem a bit odd, doesn't it, though?
  • The garage paradox I finally understand the question about "Imagine you drive a long car really fast into a short garage. The car fits from the reference frame of the garage, why can't you park it?" If you want to stop the front and rear of the car at the same point in time from the reference frame of the garage, you'll be stopping them at different times in the reference from of the car - namely stopping the front rather earlier than stopping the back!
  • How come we get contraction if the Lorentz transform increases coordinates? The Lorentz transformation has x' = (x + vt) / (1-v^2)^0.5. The term on the bottom is less than 1, so we're stretching out x coordinates. But we're supposed to have a contraction. What's going on? While the transform changes x coordinates, it also changes t coordinates. The transformed points that have the same t' coordinates have x' coordinates that are closer together. I should draw a diagram.

I've got some more complicated bits to cover (even before I get onto the second half of the book), but that'll do for now.

Posted 2015-12-19.

Another knitting project

It's been 3 years since my last knitting project, and I recently bought a book on knitting, so it seemed time to create a new project. Plus we had this weird multi-coloured wool lying about the place.

Last time, I knitted and only knitted. I never learnt to purl. This meant I ended up producing garter stitch, which is frankly not as pretty as the stockinette everyone's used to. This time, I learnt to purl!

(The book recommends using plain wool when learning, but this multi-coloured stuff's pretty good, since the colour changes make it all a bit clearer as to what's going on.)

Actually, I tried to do a bunch of fancy stitches, and tended to end up with accidental yarn-overs when switching between knit and purl within a row, so I just fell back on doing a bunch of stockinette. Caroline then suggested making mini circular scarfs for the kids (or "snoods", although I can't face the term), so that's what I did.

Once I got the hang of stockinette I put in a bit of switching over the stitches in order to create initials on the scarves to distinguish them. The first one I just tried creating a region of inverted stockinette, but that didn't work so well - the way it tends to curl in opposite directions at the sides and ends meant that some bits bumped up, and some down. For the second one, I tried doing the initialed area in garter stitch. It more or less worked. Hey ho.

End of step one, it looks liked this:

You can see they look a little, err, uneven. Rather like my first scarf. Apparently the secret is "blocking", which is a fancy term for pinning it out and getting it wet and making it dry in the right shape. Doing this properly involves threading stuff around the edge to to get a nice straight edge, but I did a lazy version:

I think they came out ok. You can see a certain amount of twisting up around the edge, but that's just what stockinette does, apparently. If I don't want that I have to put some fancy edging on. I'll live.

Finally, I stitched up the edge to create the loop, and I have a couple of home-made if slightly naff Christmas presents! If Daddy can knit, perhaps this will convince the children that women can be astronauts and doctors....

Posted 2015-12-16.


I was in the mood for another Magnetic Scrolls adventure, and had tried to get into this a few times before without much success, so I had another go at Corruption. I did make a fair amount of progress, before trying to work out if the hospital section was a red herring or not, and finishing off the game with a walkthrough.

As you might guess from that, the game did not utterly enthrall me, even if it was reasonably fun! It's actually a rather small game, compared to Guild of Thieves or Jinxster. The trickiness is in how the game is heavily time-oriented, with certain events happening at certain times. You need to be at the right place at the right time to collect all the evidence you need to show your innocence.

As such, it's actually much more of a scavenger hunt text adventure than it initially looks. On the other hand, the way to find out what you need to do, when, seems to largely consist of following people around, or hanging around seeing what happens at particular times, in order to construct the correct walk-through. In other words, to complete the game, you must make notes from other runs, and then make the character act like a psychic. I'm not a great fan of this approach.

Finding the "treasure" was in a few cases counter-intuitive, as you must not only work something out, but make the evidence obvious to your player character. In other cases, it was simply a bit obscure.

There's a fair amount of filler in what is even then a fairly small game. Irrelevant locations abound, as do red herring NPCs. Compared to GoT and Jinxster, it's a real disappointment. It's very much not a game I'd want to try to complete without a walkthrough, but it's reasonably fun for a quick explore with hints.

Posted 2015-11-23.

A frame for my cross-stitch

So, some time ago, I did my Head Over Heels cross-stitch, but I never found a nice way of presenting it and protecting it from the elements. No standard picture frame would fit. And now I have a frame!

Work has a "Makers Lab", and my original plan was to use the little CNC milling machine to make the appropriate shape (a hole on the front and a recess on the back). Fortunately, an experienced guy turned up, and advised me it would be slow and a relatively steep learning curve to do that (I should start off with playing about with other stuff using foam first, to get experience). Instead, I was pointed back to the laser cutter.

I was already going to use the laser cutter to cut the window, from some spare 3mm transparent acrylic. So, I broke the rest of the design into a set of 3mm layers, and laser cut some 3mm ply for the frame shape plus a stand. I stuck it all together with copydex (probably the wrong adhesive!), and this is the result.

I really am pretty happy with it. I considered painting it, but Caroline rather liked the raw laser-cut look. This now sits happily on my desk at work, where no-one has expressed the slightest interest. There we go.

Posted 2015-11-21.

Haskell + Laser = Penrose

I've always wanted a set of Penrose tiles, and now I've made some! I wrote a small Haskell program to generate a regular tessellation of kites and darts (not a Penrose tiling) as an SVG, and then used the laser-cutter at work to cut the shapes out of 3mm perspex. I actually cut out a full blue set (kites and darts) and a full yellow set (kites and darts), and mixed them, so I now have two sets! One for home, and one for work.

I learnt a couple of things: 1. The ratio of kite and dart pieces in use tends to the golden ratio. I've cut out the pieces in a 1:1 ratio, and end with some spares. 2. Putting the pieces into a Penrose tiling is not quite as easy as you'd think. 3. But it's kinda addictive! I'm most tempted to cut out a pile more in order to be able to make bigger patterns.

Posted 2015-10-11.

Finishing the plane

I've finally finished the model aeroplane that I posted about previously. Actually, I finished it a while ago, but I've only now got the energy back to post!

It turns out that the later and later stages of model aeroplane construction are less and less rewarding, at least for me! Gluing wood into shape is fun, covering with paper is fiddly, and decoration is tedious and when I do it, it produces underwhelming results. Still, it is done.

It's been undercoated, painted, details drawn on, decals applied, varnished and final features added. Final features first: I tacked on the antenna as a somewhat ad hoc extra, and the cockpit was made from painted balsa strips, since the original plastic cockpit somehow was crushed. Varnishing was the same as painting.

Decals were just like the "soak in water and slide onto surfaces" transfers you'd get in cereal packs in the '80s. They still have a tendency to tear, and they don't look great, but they're ok. I drew the edges of control surfaces on with a pen and ruler, which just reveals how poor I am with a pen and ruler. And then the lines ran a bit when water from the decals got on them. I guess the lesson is to do decals before lines.

The main faff was the painting. Rather sillily, I did it with an airbrush. I wanted the best finish I could manage with my limited skills, and, hey, I got to play with a new tool and attempt to learn a skill and understand the technology. Airbrushing is pretty fun, but I'm... not skilled with it. I got a cheapy airbrush, which wouldn't help, but it's easy to get it to clog up, and condensation can make it end up somewhat sputtery.

Still, it's done now!

Posted 2015-10-10.

DIY laptop case

I've finally finished the DIY laptop case project that I'd been working on, and moreover had the time to recover from it.

The plan was to create a fabric case for my ancient Macbook Air, with the external cover using pinstripe fabric at an angle, and the inside using a patchwork of Clarissa Hulse fabric.

Overall, I'm pretty happy about the result, although I'll admit the quality of work's not great:

After comparing a few alternatives, the design I used came from here. I decided on a plastic zip so as not to damage the notebook, and learnt far too much about the varieties of zip design before promptly forgetting it all. I decided to go for a nice chunky zip in bright orange as a bit of a contrast to quiet pin-stripe.

Anyway, I was never going to produce a result as good as someone with proper sewing experience, and as I'm making a one-off the lessons I learnt are somewhat lost, but I really wanted to create my design myself, and, well, it was an interesting learning experience. :)

Here are some things I learnt:

  • Working with fabric is hard. Constructing something that's the right shape from wood might be difficult, but when the material keeps changing shape, scrunching up, stretching, etc., it's a right pain.
  • Also, you're kind of expected to create more complex shapes - the fabric will have changes of direction and rounded corners, whereas with other materials you can just leave it all nice and square. In short, smooth corners are hard.
  • Clarissa Hulse fabric off-cuts patch-worked together produced the effect I wanted. We considered the fabric for curtains, but big, expensive silk curtains would have been destroyed by the children by now, so not doing that was a good move.
  • Chunky zips are a right pain. They want to lie flat. They certainly don't want to be part of a 180 degree turn-around at the edge of the case. They come with chunky strips of heavy-duty material attached, in order to zip big, heavy things effectively, and that's really bad for this kind of application. I trimmed off what I could, especially at the ends, which helped somewhat.
  • Don't let people close. The finishing, especially around the corners of the zip, is bad.

Despite all that, it was a fun project.

Posted 2015-08-15.

My ill-considered thoughts on golang/go

They try hard to make Go not hard. They leave out hard things, and say to do things in a not hard way. They have strong views and are very clear as to how to write good things in Go.

It has strict types as weak types are bad, but poor strict types as good strict types are too hard. So, I can't make my own safe map that holds a type A or a type B. But Go has maps built in. Could this be why? Poor types make me sad.

When I write Go, it feels like all short words of one sound. And they say this is like how to speak to a small child. And I shake my head, I give up.

Writing Go feels like writing using only monolsyllabic words because somebody heard that you should make things easy to explain to a child, and short words are easy. Of course, you don't speak to a child with monosyllables, you speak simply and clearly.

I read a paper once that tried to explain the problems with Kelly criterion, using words of one syllable. It was doing that to be condescending, and unsurprisingly it just made the arguments more obscure. Go feels like that to me.

Fundamentally, Go is retro-futuristic. If you want a language in the footsteps of C and Awk, if you were clobbered with C++, Java and Python and wanted the future Bell Labs promised you, this is is the language for you.

However, the changes don't really progress beyond the '80s. The way of representing types is perhaps an improvement on C, but is just stupidly weak beer compared to, say, what Haskell gets up to. Knowing what's immutable through constness or values just assigned once is great. Go does not have that. It has pointers. Pointers with "nil" values allowed. As mentioned above, no sane generics.

The interface model is insane but fun. It's not what I'd put in a strictly-typed language. Pointers allow out and in-out parameters, but you can also return tuples... but there are no tuple types.

Mind you, tuple types might encourage you to factor out common functionality, such as error-handling. All error-handling should be as long-winded and tedious as possible, as otherwise you're not doing it right. (In a similar vein, you should be writing full explicit error messages for when your unit tests fail. Having a compact way of expressing your invariants is not the proper grind.) Exceptions are bad, because people don't use them properly. Of course, in C people always checked returns codes, so I can see why they have returned to this approach.

Except, of course, that they do have exceptions, wrapped up under a different name and twisted up so that you're not tempted to use them. I do rather like "defer", though, which is almost as good as actually having RAII or some other "with" structure.

The channel-based communications mechanisms and go-routines are nice. Conceptually not new to users of Occam or Erlang.

Everything I see in Go, I see condescending design choices made by someone with confirmation bias. They've cleared away all that is bad in modern languages, returning to and enhancing those things that are good. And ignoring all the things that are clever and different.

In some ways, the name says so much. A clear lesson from everything else is "Choose a name that is easily googled". However, this knowledge comes from after 1990, and the thing's called "Go".

What would I use instead? I'm a bit of a Haskell nut, despite its deficiencies. I expect ocaml is pretty good, but need to look into it. I'm getting increasingly interested in Rust.

To be perfectly honest, it does well as a deliberately mediocre language. It's probably quite good as a first language - better than Python at any rate. In the end, what grinds me down about it can be described in two words: parochial condescension.

Posted 2015-08-11.

Lego Mindstorms is Trigger's Broom

Lego is not quite Trigger's Broom, or rather the name is, but the toy itself is not. Lego Mindstorms shares the name with the original toy, but is basically incompatible, having been incrementally redesigned over the years.

So, I've been out of Lego for well, most of twenty years - a generation - and am getting back into it with my children. I received a fantastic Lego Mindstorms set as my leaving present from my last job, and decided to build it with them, which meant waiting for the Summer holidays. The holidays have arrived, and we're now playing with it.

It took a while to realise it, but, well, look at the pieces:

The top piece is traditional old-school Lego. The bumps on top allow you to stack pieces. Good in compression, poor in tension. The second row is Lego Technic from my childhood - the holes can hold axles, or rivet-like pieces to bind the bricks together, like a spanner-less Meccano. The third row is Lego Mindstorms - it's got the holes, but it's got no bumps. You can't directly use old-school Lego with Mindstorms!

I can kind of understand why they did this - the traditional Lego connections, being poor in tension, are useless for the kinds of applications Mindstorms are for. On the other hand, it seems really weird to have a Lego-branded product that, well, doesn't plug with Lego.

Posted 2015-07-25.

A painted cube

A friend said I should paint the 3D-printed Weighted Companion Cube, so I did. I had the paints left over from a model kit from my childhood (see previous post), but I'd never really used them before, especially on something small. For some inexplicable reason I hadn't spent my early adolescence painting tiny model orcs, so the painting was something of a lesson for me. I learnt:

  • Twenty-year-old model paints work fine.
  • A loupe is really useful.
  • I would have been better off giving it a comprehensive base-coat of white at the start. The grey shows through pretty easily, made worse by the bumpy surface (see below).
  • Working at a tiny scale is very fiddly, but with a super-pointy brush previous experience playing at watch-making came in useful.
  • It's really fiddly.
  • At this scale, the printing ridges are large. It really does want to be smoothed down (acetone trick?) before being painted.
  • It takes far too long to do.

Without further ado, the fruits of this labour are below. To be honest, I reckon it looks a bit better in real life. :)

Posted 2015-07-19.

Constructing things (planes and cubes)

Recently, I've been constructing things. A few months ago, between jobs, I popped down to where I grew up to collect the last of my stuff. It's been some time! However, I didn't really want to pull things out until we'd bought a place, to avoid moving everything time and again. Then, when we'd bought a house, time for this kind of thing was incredibly limited. Anyway, the stuff's finally here.

Amongst all this stuff was a balsa-wood model aeroplane that I was constructing with my father, a project that must have stalled in the early '90s, if not before. The fuselage had been glued up, but that was it. Being something of a completionist, I worked through the rest, and it's now ready to paint!

It's not a brilliant job, but it makes me happy. Things I discovered include:

  • Assembly of the balsa wood frame is quite rewarding - cutting the balsa is simple, balsa glue is unyucky and wonderfully quick setting, and you can build up a shape fairly easily.
  • Covering with tissue paper is a PITA. I avoided traditional dope, going instead for PVA glue, which seems to make a nice substitute. Covering the fuselage in small pieces was incredibly tedious, but simple and the result wasn't bad. Covering the wings was a right faff. This is also, I think, where dope may have an advantage, since I think it can help tighten up the paper on the wings. Instead, the paper is not exactly taut on my model.
  • It was also not clear how to deal with the edges of the paper - do I go for sharp edges and a little bump, or something a bit more torn in order to try to smoothly transition? You can see the dots on the leading edge of the wing where my scalpeling did not go to plan.
  • A 3D printer comes in handy - those wheels were printed and painted, as one of the original wheels in the kit was lost over the decades.

"A 3D printer?" you say? Why, conveniently work has a 3D printer for our use, which looks like an extremely fun toy. It has the advantage that you can set it off, go do some proper work, and then come back when the print is done.

My first test was a Weighted Companion Cube, because I'm a fan of Portal. My first attempt went wrong when I failed to click the "add supports" button, leading to the printer attempting to doodle into space. One quick cancel later, and a reslice, it was off. With a well set-up high-end consumer printer, printing a small part, it seems that the whole thing's near idiot-proof.

This is the result. It's about an inch cubed:

To my eyes, the quality is very good. You can see the printing artefacts, but they're relatively small. I am extremely tempted to try the acetone vapour smoothing trick, and see how it goes.

Posted 2015-07-19.

Solving Rubik's Magic: Master Edition, Part 2: End game

Finally, the solution! This stage involves some moves that are relatively tricky to explain, and if I were living on the cutting edge of ten years ago, I'd just attach a video of the moves. As it is, I won't, and instead I'll find someone else's description.

As it turns out, after exploring the complete space of 2x6 configurations, the only move required to get to a state from which we can solve the Master Edition is a "-X". This takes us from the initial back view:

To a configuration where you can see the core of the solved puzzles:

From here, you can perform a twist very similar to that used when solving the small magic, to move to an "L" shape:

Finally, you can do two of the "bend the corner round" moves that you use to finiah the small magic, to bring it into its final configuration:

I found the website in the links after writing everything else up, when I was looking for an easier explanation of the more complicated moves. Interestingly enough, the moves described there are basically the same set, plus a "row swap transform", which it describes as also implementable with X and O. So, it appears my analysis is either "unoriginal" or "correct", depending on how you look at it.

Posted 2015-07-05.

Solving Rubik's Magic: Master Edition, Part 1: Group theory

In this post, I'm going to look at moving between the possible 6x2 flat configurations. For everything here, I'm assuming that you're viewing the Magic joined-up-rings-(starting position)-side-up. As the pattern's a bit distracting, I'll be using a schematic view of the Magic:

The numbers represent the position of squares initially, and the dots represent a particular edge. Initially, I'll place the dots on the outside, have the top-left square be square number 1. Note that the 3 highlighted squares in the top left more than define the position of everything else (see my previous post for details).

We're going to see what positions are reachable given combinations of three basic moves. The first, I'll call "X", after the way the squares windmill, and it's simply achieved by folding the Magic up, folding one square down, and another up:

X simply moves all the pieces around one step, without any rotation or fancy changes:

The next move, I'm going to call "O", since we make the Magic into a loop. Just fold the Magic in half, then slink it one square along. Note that it will then open up the other way:

So, this move can be used to change the orientation of the pieces:

Note that so far, we can only rotate a piece by 180 degrees. Next move, I'll call "S" for "square", as we do a move that makes it into a square, then unfold it again (90 degrees around) to end up in a different shape:

This move rearranges stuff quite a bit, and includes a quarter turn, which should allow us to reach more configurations:

So, given these basic moves, can we create all configurations? Well, we can if we can move any piece number to the top left, rotate it arbitrarily and switch between clockwise and anti-clockwise numbering...

  • Moving a piece to the top left Simply do "X" repeatedly.
  • Rotate the top-left piece S, -X, -X, -X (-X being the undoing of an X move).
  • Change direction of loop O, X, X (also rotates the top-left piece by 180 degrees, but you can fix that by doing the rotate step twice).

Given this, we can make any 6x12 configuration, so as long as we can go from a 6x12 to the final "W" shape, we can solve the puzzle. And that's the next post.

Posted 2015-07-04.

Solving Rubik's Magic: Master Edition, Part 0: Counting configurations

This is old, old news to everyone but me. Growing up, I loved my Rubik's Magic, but I never played with the Master Edition. Moreover, I never tried to analyse it mathematically. So, I decided to finally play the thing, and try to understand it.

Solving it wasn't difficult, but getting around to writing it up has been a right pain. :) I thought I'd start with something very simple: Counting the number of configurations. Specifically, the number of 2x6 flat, rectangular configurations (like the starting position).

First a couple of fairly obvious constraints: Whenever the puzzle is laid flat, it's always with the same set of pieces facing up - there are two "sides", and pieces don't move between the sides. Moreover, each piece is always connected to the same other two pieces - the sequence of pieces in the loop is always the same.

So, we lay it flat in front of us. We can choose either side to face up. There are twelve possible pieces that can go in the top left. This piece can be one of four rotations. That fully describes the configuration of the top-left piece.

What about everything else? The neighbouring pieces will always be the same, due to the limitations of the "loop". However, this loop could be running clockwise or anti-clockwise. However, once that's determined, everything else is determined. The orientation of all the other pieces are full determined by the orientation of the top-left piece - as it rotates, all the others rotate, like gears.

This gives us 12 x 4 x 2 = 96 configurations. However, the puzzle itself has a rotational symmetry of a half-turn, so really that's just 48 configurations. This is far fewer than I was expecting! By similar logic, there should be 32 configurations for the vanilla magic.

This assumes, of course, that all the configurations are reachable - this is an upper bound, but perhaps some configurations can't actually be achieved. As it turns out, all the configurations are reachable, and that's what I plan to demonstrate next time...

Posted 2015-06-28.

Two Weeks of Google and a new phone

So, I've been two weeks at Google, and one side effect I hadn't really noticed before is that my own home projects are getting somewhat sidelined by the fire hose of learning new stuff at work. Ho hum.

On the other hand, I've got a fancy new work phone.

It's a bit bigger than the last phone I had.

On the other hand, the technology's moved on tremendously, and it's really nice to be browsing the web on a mobile without feeling like a second-class citizen. The downside is moving over to the Android ecosystem is faff. The apps are ok, but moving my music and photos over is a pain. Still, slowly getting there...

Posted 2015-06-17.

One Week of Google

One week of Google, and it really is as people expect. I've learnt a whole pile of cool stuff, but as described in How Google Works, there is much internal transparency, but leaks are taken extremely seriously. So, I'm not going to reveal pretty much anything. Oh, and memegen is as silly as the book makes out.

5/5. Would be recruited by again.

Posted 2015-06-06.

Paper round: And then some

I may have finally written up the papers I read some time ago, but I still have a number of papers from that pile, plus a couple more recently-added ones. Time to discuss them:

  • Mosh: An Interactive Remote Shell for Mobile Clients This paper reminds me how I don't tend to take an innovative approach. I thought of ssh as good enough, and am generally suspicious of reinventing the TCP wheel. Then, this paper shows how you can make remoting over flakey wireless connections much better if you try. D'oh. ("mosh" itself is rather nice, but I'd really rather like good scrollback.)
  • Practical Byzantine Fault Tolerance One of the classic papers on distributed systems. The bit on committing operations is very plausible, but I look at the section on changing views and... its correctness is not intuitive to me. Tricky.
  • Data Compression Using Long Common Strings Data compression is often rather tricky, but as you might expect from Bentley and McIlroy, this is both simple and effective. Fun.
  • Large-scale cluster management at Google with Borg And this one suddenly looks very relevant to my work! The first section or two seemed a bit vague and naff, but the details fill in over the later sections to give a reasonable impression of what they had and now have. The future work section (especially Kubernetes) looks very interesting, and the references should give me plenty to chew on.
  • Breakthrough silicon scanning discovers backdoor in miliary chip A somewhat melodramatic title sits at the top of a fundamentally unremarkable paper. Unremarkable, perhaps, but still fun. The "backdoor" is in an FPGA used in, among other things, military technology, allowing the bitstream to be read out. Looks like an undocumented debug feature. The interesting things are a) how the advertising material lies so strongly about the security b) the technology used to identify the undocumented feature.
  • Trafficking Fraudulent Accounts: The Role of the Underground Market in Twitter Spam and Abuse Yet another fun little paper investigating the online criminal economy. (If you like this, go read all the Silk Road reporting - not directly related, but also interesting.)
  • TCP ex Machina: Computer-Generated Congestion Control Another paper by the guy who did Mosh, although I came across this one first. In short, by applying a simulate-and-optimise approach to TCP congestion control, something can be produced which appears to work rather better than standard (human-designed) congestion control algorithms. There's lots of interesting stuff here. Is the evaluation biased by the fact that it's using models not entirely dissimilar to the ones used to do the optimisation, leading to over-fitting? Can we know it's not going to have horrible corner cases because it's not human-designed? When setting up an optimisation problem, how the problem is framed will feed into the result, and that's rather interesting. For example, packet loss is not used. Instead, RTT variation is used to detect queuing, which is rather nice given the problem of buffer bloat. All rather cool.

Posted 2015-05-31.

Paper round: Odds and ends

Around, er, two years ago, I reviewed a bunch of papers, and noted some other topics I should learn more about. I read up on some of those topics shortly afterwards, but never actually put together a round of paper reviews covering highlights of what I'd read since then. This is it. There are a lot fewer papers than I should have read, but on the other hand, there's a lot of cool stuff that's just readable as web pages now, so I almost feel less embarassed about it...

Data structure and algorithms

  • A Digital Signature Based on a Conventional Encryption Function - Merkle This is the origin of Merkle trees (hash trees). The hash tree idea is rather useful in many situations, but it's really not a huge part of the paper, which is another clever crypto algorithm paper. Fun, but less relevant than you'd expect for hash trees.
  • "Hash tree" in Wikipedia I'm reviewing Wikipedia pages now?! Apparently. Anyway, a much more useful introduction to hash trees than the above paper, even if it misses out fun irrelevant crypto.
  • "Error detection and correction" in Wikipedia While I'm at it, error detection/correction codes are nutty, and I've never found a decent introduction to them. On the other hand, reading a few Wikipedia pages is actually quite a good way to get a basic idea of the landscape. I also read the pages on Erasure Code, and Turbo Code. Turbo codes are nutty magic. I need to read a proper book on codes.
  • Turbo Codes - Emilia Kaesper Another introduction to turbo codes. It explains how they work, but doesn't give a good intuition as to why they work. They continue to be magic to me.
  • Space/Time Trade-offs in Hash Coding with Allowable Errors - Bloom Bloom filters are awesome, and I'm embarassed I didn't know about them sooner. They should have been somewhere on my undergrad algorithms course. This paper introduces them. Read it.
  • The Log-structured Merge-tree - O'Neil et al The LSM-tree is basically "Keep multiple copies of the data in a hierarchy (e.g. in-memory and on-disk), and then batch up and merge through, to allow high-throughput writing with querying." The paper is, I thought, disappointing - long-winded and not terribly inspiring.
  • Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web Ugh. An ugly long paper title, presumably influenced by "it must be a trendy web technology". This paper covers consistent hashing and random trees, but it's only really consistent hashing that I wanted to learn about. The paper hides the intuition behind it pretty badly compared to, say, the Wikipedia page.

Google papers

I'd previously read about GFS, Bigtable etc., as well as Dynamo and a few others, but there were plenty more Google papers to read. Bear in mind I read these a couple of years before my Google start date:

  • Spanner: Google's Globally-Distributed Database This is Google's replacement for the famous BigTable and Megastore systems. You can tell it's a big deal by the number of authors on the paper! Sadly, however, I don't get the big deal. There appear to be two impressive angles: The timing aspect, and SQL-like querying. The timing aspect seems mildly unimpressive to me - if you synchronise your clocks, you can bound when each component sees things. Er, great. And the SQL-like querying angle isn't really covered by the paper. So, the level of innovation, as presented by the paper, underwhelmed me. Ho hum.

  • Experience Report: Haskell as a Reagent - Pop Having used Haskell for a production system, I had some interest in seeing how other people ended up using it. In the end, I found the paper a little unexciting, but competent enough. Oh, and Haskell was being integrated with Python. Ick. Since reading the paper, I've become a little more interested in sysadmin approaches at Google. Ahem.
  • A New ELF Linker - Taylor This describes the "gold" linker. Pretty cool work by the guy who worked on the original GNU "ld".
  • Modular Software Upgrades for Distributed Systems - Ajmani et al Another Google one. Basically "How do you upgrade complex, long-lived distributed systems?" "Carefully." Nice ideas, but just a little more formalisation than was really necessary.


  • The Athens Affair (IEEE Spectrum) Co-authored by a co-author of the FPF paper (the rather prolific Diomidis Spinellis), it's a discussion of the rather fascinating hack of a Greek cell-phone network. It's one of the lesser-known publicly-known probably-sponsored-by-the-US hacks.
  • Barbarians at the Gateways - ACM Queue An introductory article on the HFT arms race and the technology it involves. Light fun.
  • Finding and Understanding Bugs in C Compilers - Yang et al Generate randomised test code for compilers, compile them, look for bugs. Collect bugs, fix them, look for patterns. Really quite interesting.

Posted 2015-05-27.

Tobin/Transaction taxes

I am, I'm afraid, now on Twitter. I read it for the links to articles, you know. Anyway, I saw this Tweet retweeted by people that I know (and generally think of as sane):

A Robin Hood Tax is a tiny 0.05% tax on transactions in the financial sector. This could raise 20 BILLION GBP a year. RT if you support this.

To me, this illustrates perfectly why anything even vaguely subtle shouldn't be discussed on Twitter. Fortunately, the Wikipedia entry on Tobin taxes does have a lot of detail. It's a bit long. I thought I'd do my take on it, even though I don't have a Nobel prize in economics (yes, I know it's not a real Nobel anyway).

I've just left a job in the finance industry after ten years, so I think I have a reasonable understanding of it, without having a huge investment in its future.

The size

First of all, I'm not sure how a tiny tax can raise mind-boggling amounts, unless because it's not a tiny tax, but actually a huge tax, pretending to be tiny. To put the twenty billion in perspective (using slightly old data), the UK's finance industry contributed sixty billion in taxes, and pays out fifteen billion in bonuses. In other words, this tax would more than take away all those evil banker bonuses everyone likes to complain about, and up the total tax take by about a third. This is not a subtle tweak, it's a pretty heavy bludgeon.

The effect

Of course, it wouldn't raise twenty billion, because unsurprisingly people's behaviour would adjust to take into account the extra costs. The possibilities I see are:

  • Don't trade A lot of trading is happens because it's cheap and convenient. With a tax, they'll trade a lot less.
  • Trade elsewhere Or you just trade in another region. This means we gain no tax, and drive a lot of business away from London. Business that does actually raise a fair amount of tax, and we'll probably lose a pile of services that go with the finance sector.
  • Trade differently Banks have a lot of experience arranging transactions to be tax-efficient. Perhaps the trading will move from directly buying and selling things (simple, now tax-inefficient) to derivatives (complex, tax efficient). Not an obvious improvement for people who don't like tricksy banking.

The "don't trade" angle is perhaps worth going into a bit more detail on, for those who don't know the area. When I was working on a precious metals gold trading system, doing a test trade, buying and selling a future for 100oz of gold, worth over $100,000, the bid-offer spread costs came to around $20. In other words, each transaction cost around 0.01% of the nominal value. FX is not exactly dissimilar. Taxing an extra 0.05% is going to strongly discourage trading in such situations.

Just because a transaction isn't necessary doesn't make it a bad idea. Banks like to hedge their transactions - they want to get rid of the risk associated with their positions, so that if prices move they don't end up losing big piles of money (yes, I know, they may not always be good at this). However, they don't hedge freely, because hedging costs money. If you up the transaction costs, hedging will cost more and it'll be done less. Banks will hedge less and take more risk. Or they'll keep hedging, but pass the costs on to their customers. It's not great, either way.

The intention

Finally, what's the point of this tax? I don't think it's really to raise money. It wouldn't raise anything like the suggested amount, due to the reasons above. It's also a very distorting tax, which will affect particular kinds of banking more than others.

Indeed, it's so distorting that it's either put together by an idiot, or it's intended to target a particular sector.

The sector that would be affected is the "flow" sector - the simplest, most straightforward products. The sale of complex derivatives such as the mortgage CDOs blamed for the credit crunch, which are much less liquid, with much bigger bid-offer spreads would not be affected by this rule. If it's a reaction to financial meltdown, it makes no sense.

Anyway, let's go with the "bad bankers" narrative, and assume that there are some people who need to have their lives made more difficult. Who is problematic in "flow"? I can see two sets of targets - bad traders and high-frequency traders.

The bad traders keep getting huge fines from the regulators. Fines and jail for wrong-doers seem the way to go here. Blanket taxing everyone involved is hardly an incentive for those who aren't crooked!

The other lot are high-frequency traders, who trade a large volume on tiny, tiny margins. They would be hit extremely hard. They're not actually bankers. They tend to be fairly small companies, operating with their own capital. The main objection is that by being faster than everyone else, they're taking their money away. However, they do seem to have reduced spreads and made the markets more liquid for small traders (i.e. retail customers). HFT basically takes money from the big players by doing what they traditionally did (have an information advantage over everyone else). So far, so meh.

What are the objections? It's socially useless? Candy Crush Saga is probably a bigger waste of time. Anyway. It's an unfair advantage? In the grand scheme of things, the resources required are not huge, and it's a very competitive area.

Let's say it's deemed bad. A Tobin tax is still not a clear winner. The big banks and institutional investors don't like HFT either. Surely they can find a way to deal with HFT? Why, yes! There are dark pools for large trades, exchanges with randomized timing to reduce latency advantages, etc. The problem with HFT may not be that they trade too much, but place too many (unfilled) orders, so you can cap the order to fill ratio. All these things can be fixed in a more targeted manner by adjusting the market mechanism. No tax needed.

So what would I do?

I don't know, as I'm not sure what the aim is. If you want to deal with the problems of flow trading, there are better ways. If you want to deal with problems outside flow trading, there are ways that are actually relevant. If you want to raise more taxes, you can try to increase the tax rates in less distorting ways, or perhaps actually reduce the opportunities for tax avoidance, and clamp down on the "borderline" tax behaviour across the whole of big business. If you want to "fix" banking post-2008, you've got to balance what you want. Extracting large amounts of money is incompatible with making the banks build up large reserves. Getting the banks to lend is incompatible with reducing the risk they take. Taxing banks heavily may not actually be very sensible if you own large chunks of them. If you don't like bankers' pay, regulate it (there are guaranteed to be unintended consquences).

In all cases, "Let's have a transaction tax" sounds suspiciously like "We must do something, this is something, let's do it".

Posted 2015-05-24.

Crowd-sourcing and the Wisdom of Crowds

The Wisdom of Crowds makes some good points about how and when a large number of people can do things better than experts. Crowdsourcing often refers to splitting work across a large number of people. However, what I occasionally see is a "crowd-based" problem-solving approach which is... not really.

For example, if you have a difficult problem, you might shove it out to the crowd. A fan of crowds might say the Netflix Prize was solved that way. However, in that sort of case, it isn't the crowd solving it, it's some bright people. You've just given the problem to some bright people, and a bunch of normal people.

In other words, crowd-sourcing like this is not really about problem-solving, it's about problem-routing - effectively packet-switching problems towards the appropriate experts, even if you don't know who they are. You feed the problem into the social graph and hope it is forwarded to an appropriate destination.

Sometimes, a crowd really is only as wise as its wisest members, but in a large crowd that can still be pretty darn wise.

Posted 2015-05-21.

The Internet is Street Art

I found this note in a file simply saying "The Internet is Street Art". I vaguely remember it from a couple of years ago when I went to Covent Garden, and saw some street performance.

My understanding of street performance, gleaned from limited experience of places like Covent Garden and the Edinburgh Fringe, is that you get in the way of people and show off. Well, it's more than that, it's moderate talent, the ability to manipulate a crowd to create a "people join the crowd to see what the crowd's for" effect, and a willingness to get in the way of those not (yet) interested. The cost of entry as a spectator is nothing, except your attention, and you're probably underestimating the value of that.

And in so many ways, this is the web. It's basically about going viral and getting a crowd. Quality is not the ultimate concern, and the only price is free. And fundamentally, the idea is to get in the way of passers-by.

I don't really like street performance. *sigh*

Posted 2015-05-21.

Linux 1.0 kernel source reading - 7: fs/exec.c and friends

For my first foray into the "fs" directory, I thought I'd try something relatively loosely coupled to the file system, and more to the rest of the kernel I've been reading: The "exec" infrastructure.

exec.c starts with various utility functions whose context will have to arrive later. Bottom-up code isn't always the easiest to understand!

It's kind of strange that "flush_old_exec" doesn't explicitly share code with "sys_exit", as they're both freeing a number of process resources. It's not exactly "Don't Repeat Yourself". (If I were designing this, in a slightly more high-level, OO and RAII kind of way, I'd separate out the structures representing the bits of process that survivce across an "exec" call, and those that don't. On "exec", I'd tear down one structure, on "exit" both.)

Mostly, though, this is straightforward code, and shows how simple the a.out format is!

binfmt_elf.c ELF is more complicated, shock. Probably best read with a copy of the ELF standard. Instead, I'll skim. "/* Now use mmap to map the library into memory. */" comment appears to be in the wrong place, after the work is done!

The interpreter-loading stuff was, unsurprisingly, a bit obscure until I read up on PT_INTERP. It still feels odd having a.out-loading code in the middle of the ELF code, and does rather seem as if there's redundancy in the code.

There are lots of long functions. It might be nice to break them into short functions with well-defined purposes. The overloaded returning of error codes and success values is a bit painful, although I'm not sure there's a pretty alternative in vanilla C.

binfmt_coff.cis written by some other person. Heavily commented, which is nice, but the comments starting in column 0 inside functions make it difficult to see where functions start and end! It refers to "coff.h", which demonstrates a consistent inability to spell "O'Reilly". "load_object" is a 450 line function? Really?

It looks like there's a bug in reading the sections - if there's a badly-aligned section, then a good one, the status code is overwritten and it'll ignore the bad alignment, I think. It probably checks again later, though. There are odd error messages on strange section counts, too, and the continual conditioning on status suggests that "goto"-based error handling may not be that bad after all!

Having said all that, the heavy commenting makes this file pretty readable.

Library-loading is much easier for COFF than ELF. If a COFF header asks to pull in a shared library, rather than execute a loader, it just uses "sys_uselib". This is presumably rather less flexible than the ELF approach, but makes for much simpler code!

Bonus 1: filesystems.c is simply a (ifdef-configured) registry of the known filesystem types.

Bonus 2: file_table.c manages the circular list of all files. For some reason, it mixes in unused file entries with the allocated ones, and generally seems slightly naff code if you ask me. Maybe reading other source will make this clearer?

Posted 2015-05-20.

Linux 1.0 kernel source reading - 6: IBCS and IPC

"IBCS" turns out to be nothing more than a "NYI" stub. And after all the iBCS compatibility stuff in signal handling!

ipc/util.c is the main entry point for sysv ipc. There's a single syscall with a switch statement. sysv ipc support is configurable, so there's an ifdef to switch to dummy code for the disbled case.

ipc/sem.c handles semaphores. The need for sem_lock and IPC_NOID seems odd to me, why not kmalloc first before fiddling a shared structure? "sys_semctl" is ugly (sequence of switches on the same command is odd). The code doesn't quite feel the usual standard of the rest of kernel.

ipc/msg.c - message queues. The business of rechecking the entry's id in "sys_msgsend" makes me nervous. It feels race-condition-like, although it probably really is a valid race condition that meets the expected interface. Much of the code is copy and paste of sem.c. Not quite sure if this is repetition is bad style or just the faff of doing this in C.

ipc/shm.c - shared memory. Again, some shared infrastructure. "shm_map" runs off the actual page table, rather than the mappings structure, which seems inefficient. It also maps in the new top-level pages while checking the existing mappings. If shm_map fails due to a clash, you'll have a pile of empty top-level tables, which is mildly naff.

One mildly tricky (and uncommented) bit of code: As far as I can tell, swapping shared memory works by getting the reference count down to 1, which represents the reference count from the shared memory object itself (the other references being from it being mapped into processes). At that point, the page can be swapped.

Overall, I was a little underwhelmed by the quality of the IPC code...

Posted 2015-05-16.

Learning modern web technology

It occurred to me that if I am to work for a web firm I should really know some web technology. My knowledge of the web was extremely out-of-date and patchy, so I thought it time to make it up-to-date and patchy. The aim wasn't to learn all the latest trendy technologies, but more what's been the backbone for a while.

The web used to be a horrible mess, but with the triumvirate HTML5, CSS and Javscript, plus modern browsers, things are a lot neater and more pleasant. To learn, I did a pile of courses on codecademy. This was rather neat as I didn't only learn a bit of modern HTML, CSS and JS, but I also got pointed at Boostrap and jQuery. I guess you can say technology is mature when it's got helper libraries on top of it! I understood the existence of JS helpers, but CSS helpers were a bit of a surprise.

Anyway, the existence of these libraries explained something of a mystery to me: Why so many websites have such similarity in style, beyond the demands of fashion. Well, they're all using the same libraries. Also, I got to find out that the basic use of jQuery is not to do with querying, but for putting animations and effects on your web pages.

It also reminds me how conventional web pages are looking now. I remember "The web is a new medium! The old rules don't apply!". And now, the web looks like magazines. Ho hum. Anyway, my website's been updated to look like all the others, using the same libraries as everyone else. It's good practice, right?

One of the things I found interesting about Javascript was quite how heavily anonymous functions are used for callbacks and the like. It's almost like continuation-passing. On the one hand, it's interesting to see bits of functional programming becoming quite so mainstream. On the other side, it shows how clunky things can be without the right abstractions. Partial application is a pain, and you can't e.g. use monads or whatever to abstract away the sequencing of callbacks.

Finally, I picked up AngularJS. I must admit, I feel somewhat ambivalent about it. For dynamic data, you've got to do things on the client-side. However, it seems to go a bit far - the codecademy tutorials encourage you to do things on the client-side that could have been done on the server-side. This seems inefficient and an unpleasant move away from the underlying document-centric view of the web. On the other hand, it's good for creating dynamic sites quickly and flexibly, without having to build server-side and client-side frameworks in tandem.

I can see this kind of mindset leading to painful mobile apps. As you can make a fairly fully-featured UI in a web browser, complete with JS implementation, why not just use that for the backbone of your app? Unfortunately, mobile phones don't have the spec of desktops. Well... I guess Moore's law is going to sort my objection out sooner or later, and you can have pretty and fast apps on your phone, at the expense of battery life.

Mostly, though, I can see the use in Angular. With modern hardware and the kind of web apps people are developing, efficient technology is beaten by RAD technology 95% of the time.

Posted 2015-05-08.

Newer entries Older entries