On editing text

Editing text is the opposite of handling exceptions; or, to put it another way, editing text is like exception handling but backwards in time. I realise this is an unexpected claim, so I hope you will permit me to explain. Although it has the ring of nonsense, there is a perfectly good sense in which it is just straightforwardly true.

Added 2014-06-18: it turns out that the story is more interesting than I realised when I wrote this, and that almost all of the technical details below are wrong. I am in the process of writing an account of what I currently believe on this subject.

Ah yes, category theory. Our old friend. Elucidating structural connections between apparently disconnected topics since 1945. Let me tell you a story.

Continue reading

Posted in algorithms, category theory | 17 Comments

Something all bash scripters need to know (and most of us don’t)

Calling all bash users. This is a public service announcement.

Here’s something you need to know if you want to write bash scripts that work reliably, but you probably don’t.
Continue reading

Posted in chatter | 28 Comments

How to record a screencast video for free on Mac OS X

It’s hard to find any detailed information on the web about how to record a screen video without buying expensive software. I found out how to do it, so here I’m going to explain what I did for the benefit of anyone else who’s trying to do the same.

Continue reading

Posted in chatter | 38 Comments

Challenging the Power of Twitter

Most of the time I use this blog to write about things I understand, so it was something of an experiment when on Sunday evening I wrote a short post about something I did not understand.
Continue reading

Posted in chatter, Mathematics | 2 Comments

Something I don’t understand about homomorphic encryption

Added later: In retrospect, now I know a little more about cryptography, I can see that my confusion here is caused entirely by the fact that I didn’t know the meaning of the technical term “semantic security”.

Ever since Craig Gentry’s seminal work in 2009, there has been a certain amount of excitement about the potential of fully homomorphic encryption. The idea, I gather, is that using a fully homomorphic encryption scheme makes it possible to perform computations on encrypted data without decrypting it, yielding an encrypted result. For example, this would make it possible to process confidential data in an untrusted data centre.

The technology is edging towards practicality as better schemes are devised, and it may soon reach the point where it’s useful in some real-world situations.

But there’s something I don’t understand. I’m hoping that someone who does understand it may come across this and explain it.
Continue reading

Posted in algorithms, chatter | 6 Comments

Computing Fibonacci numbers using Binet’s formula

A few months ago I wrote something about algorithms for computing Fibonacci numbers, which was discussed in some of the nerdier corners of the internet (and even, curiously, made it into print).

Several people suggested that Binet’s closed-form formula for Fibonacci numbers might lead to an even faster algorithm. That’s an interesting idea, which we’re going to explore in this post. So, what is Binet’s formula? It goes like this:

\begin{array}{r@{\;}c@{\;}l}\mathop{\mathrm{fib}}(n)&=&\displaystyle\frac{\varphi^n + (1 - \varphi)^n}{\sqrt{5}}\end{array}

where \varphi=\frac{1+\sqrt{5}}{2} is the golden ratio.
Continue reading

Posted in algorithms, Fibonacci numbers, Mathematics | Tagged | 9 Comments

Counting small mazes

Before we get into general algorithms for counting mazes, I thought it would be interesting to do some small cases by hand. It’s quite fun to do, and it’ll give us a few numbers to check against the results of more general methods.
Continue reading

Posted in mazes | 3 Comments

Counting mazes: before we begin

If you’re following the maze series, I hope you’re persuaded that thinking about how to count mazes is a reasonable line of attack on the random access problem.
Continue reading

Posted in Mathematics, mazes | Leave a comment

Random access to mazes: plan of attack

In the last post, I explained what I’m trying to do: to assign each maze an index number in such a way that we can generate a maze given its index number, and find out the index number of any maze. One way to think of it is as a perfect compression algorithm for mazes.

But how can we do that? There are a huge number of possible mazes on any decent-sized grid, so it’s not feasible to loop through them one-by-one.
Continue reading

Posted in Mathematics, mazes | Leave a comment

What’s all this about mazes? A statement of intent.

I’m trying something that I think is going to be fun and interesting – and, who knows, maybe even useful.

I want to write a program that allows “random access” to all possible mazes, and does it quickly enough to be practical. I think I know how it can be done. That’s why I’m writing about mazes now.
Continue reading

Posted in algorithms, mazes | 5 Comments