It's more than two months since I last wrote a blog article. I've been ridiculously busy since then and things are only just now calming down. It now looks as though I'm going to try something new, at least for three months or so, and that should provide more time for blogging. I…

by Robert Harris; Laurent Binet & Sam Taylor

These two books are tied together by the name of Reinhard Heydrich. I can't think of a polite way of describing Heydrich. He was one of the architects of the Holocaust, a fervid Nazi, and an all-round total bastard. Hitler called him "the man with the iron heart", which gives you some kind of idea of what kind of a git he was.

In the real world, Heydrich dies in 1942 from injuries sustained during an assassination attempt by Czech and Slovak commandos while he was "Acting Reich Protector of Bohemia and Moravia". In the world of Fatherland, he survives, the Germans win the Second World War and Europe languishes under Nazi rule, with a sympathetic administration in the USA led by Kennedy (père rather than fils) providing no effective check on their activities. Heydrich continues in his role as second-in-command of the SS and goes on being as much as a bastard as ever.

A useful but little used feature of Haddock is the ability to include inline images in Haddock pages. Here are a few examples. You can use images for diagrams or for inserting mathematics into your documentation in a readable way. In order to use an image, you just put <<path-to-image>> in a Haddock comment. The image can be of any format that browsers support: PNG, JPEG, SVG, whatever.

by Gerald Jay Sussman & Jack Wisdom (with Will Farr)

This book follows very much in the mould of Sussman & Wisdom's Structure and Interpretation of Classical Mechanics in that it's an attempt to take a body of mathematics (differential geometry here, classical mechanics in SICM) and to "computationalise" it, i.e. to use computer programs to make the mathematical structures involved manifest in a way that a more traditional approach to these subjects doesn't.

This computational viewpoint is a very powerful one to adopt, for a number of reasons.

I recently read The Quest for Artificial Intelligence by Nils Nilsson. Interrupting a fairly linear history of the AI field is an interlude on some more philosophical questions about artificial intelligence, minds and thought. Searle's Chinese Room, things like that.

I got to thinking about some of these questions on my daily peregrinations with Winnie, and I started wondering about the scales that are involved in most discussions of minds and AI. Searle talks about an individual person in his Chinese Room, which makes the idea of some sort of disembodied intelligence actually understanding the Chinese sentences it's responding to seem pretty absurd. But is that in any sense a realistic representation of a brain or a human mind?

In keeping with my upbringing as a baby physicist, I'm going to take a very reductionist approach to this question. I want to get some idea of exactly what the information storage capacity of a human brain is. I'm deliberately not going to think about information processing speeds (because that would involve too much thinking about switching rates, communication between different parts of brains, and other biological things about which I know very little). I'll treat this in the spirit of a Fermi problem, which means I'll be horrifyingly slapdash with anything other than powers of ten. There will be big numbers.

After releasing the arb-fft package last week, a couple of issues were pointed out by Daniel Díaz, Pedro Magalhães and Carter Schonwald. I've made another couple of releases to fix these things. They were mostly little Haskell things that I didn't know about, so I'm going to quickly describe them here. (I'm sure these are things that most people know about already...)

I was obscurely disappointed to discover that I wasn't the first person to come up with "MOOCopalypse". I think I could claim first dibs on "MOOCaclysm" if I wanted, since there are no Google hits for it, but it's not quite as good.

Unless you've been living under a rock for the last couple of years, you've probably heard of MOOCs (Massive Open Online Courses). These are courses offered online by universities or other suppliers, intended to bring high-quality higher education resources to a wide and varied audience. I've done a few of these courses: Peter Norvig and Sebastian Thrun's Stanford AI course, one on fantasy and science fiction, and more recently Jeff Ullman's automata theory course and another on general game playing (about which I'll write something once I've had some time to work on the software I developed as part of the course).

After thirteen blog articles and about two-and-a-half weeks' equivalent work time spread out over three months, I think it's time to stop with the FFT stuff for a while. I told myself when I started all this that if I could get within a factor of 20 of the performance of FFTW, I would be "quite obscenely pleased with myself". For most , the performance of our FFT code is within a factor of 5 or so of the performance of the vector-fftw package. For a pure Haskell implementation with some but not lots of optimisation work, that's not too shabby.

But now, my notes are up to nearly 90 pages and, while there are definitely things left to do, I'd like to move on for a bit and do some other data analysis tasks. This post is just to give a quick round-up of what we've done, and to lay out the things remaining to be done (some of which I plan to do at some point and some others that I'd be very happy for other people to do!). I've released the latest version of the code to Hackage. The package is called arb-fft. There is also an index of all the posts in this series.

In this article, we'll finish up with optimisation, tidying up a couple of little things and look at some "final" benchmarking results. The code described here is the pre-release-4 version in the GitHub repository. I'm not going to show any code snippets in this section, for two reasons: first, if you've been following along, you should be familiar enough with how things work to find the sections of interest; and second, some of the optimisation means that the code is getting a little more unwieldy, and it's getting harder to display what's going on in small snippets. Look in the GitHub repository if you want to see the details.

In the last article, we did some basic optimisation of our FFT code. In this article, we're going to look at ways of reordering the recursive Cooley-Tukey FFT decomposition to make things more efficient. In order to make this work well, we're going to need more straight line transform "codelets". We'll start by looking at our example in detail, then we'll develop a general approach.

I haven't done one of these for a _long_ time, but I have a big old pile of interesting things I've read recently. I might make this a weekly thing -- Harry Connolly does a Friday Randomness roundup and there's always something interesting or weird there. I don't think I can…

Based on what we saw concerning the performance of our FFT code in the last article, we have a number of avenues of optimisation to explore. Now that we've got reasonable looking scaling for all input sizes, we're going to try to make the basic Danielson-Lanczos step part of the algorithm faster, since this will provide benefits for all input sizes. We can do this by looking at the performance for a single input length (we'll use ). We'll follow the usual approach of profiling to find parts of the code to concentrate on, modifying the code, then looking at benchmarks to see if we've made a positive difference.

Once we've got some way with this "normal" kind of optimisation, there are some algorithm-specific things we can do: we can include more hard-coded base transforms for one thing, but we can also try to determine empirically what the best decomposition of our input vector length is -- for example, for , we could decompose as , using length-2 base transforms and seven Danielson-Lanczos steps to form the final transform, or as , using a length-16 base transform and a single Danielson-Lanczos step to form the final result.

So far in this series, we've been looking at code piecemeal, writing little test modules to explore the algorithms we've been developing. Before we start trying to optimise this code, it makes sense to put it into a Cabal package with a more organised module structure, to provide a sensible API and to make a few other small changes.

From now on, the code we're going to be talking about will be the arb-fft package, which is hosted on GitHub. In this article, we'll be talking about the version of the code tagged pre-release-1. (We'll be uploading a version of the code to Hackage once it's ready, but there will be a few pre-release versions that we'll look at before we get to that point.)

by Douglas Hoftstadter

I first read GEB about 25 years ago, as far as I can remember. I'm not sure how much I took from it then (I was about 16 years old and knew a little bit of maths, but it was my first exposure to logic and the theory of computation), although I do remember the dialogues and all the wonderful Escher pictures.

I picked up a copy again recently as a result of reading an interview with Hofstadter in The Atlantic. The book has aged really well, with just a few technological fossils from the 1970s (record players playing records that they cannot play, for instance). Hofstadter has a timeless and almost overwhelmingly fecund imagination, bubbling over with novel ideas that seem to pop up from nowhere. His description of the thought process that led to the construction of one of the dialogues (each of which is modelled on a piece of Bach's music and attempts to explore questions of linguistics or metamathematics on a number of levels at once) gives an impression of a mind of almost obsessional twistiness, trying to pack as many ideas as possible into the smallest possible amount of text using puns, structure and patterns at all available levels. It's quite wonderful.

The code from this article is available as a Gist

In the last article in this series, benchmarking results gave a pretty good indication that we needed to do something about prime-length FFTs if we want to get good scaling for all input sizes. Falling back on the DFT algorithm just isn't good enough.

In this article, we're going to look at an implementation of Rader's FFT algorithm for prime-length inputs. Some aspects of this algorithm are not completely straightforward to understand since they rely on a couple of results from number theory and group theory. We'll try to use small examples to motivate what's going on.