How to record a screencast video for free on Mac OS X 10.7 ‘Lion’

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.

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.

Something I don’t understand about homomorphic encryption

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.

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:

where is the golden ratio.

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.

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.

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.

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.

The worst algorithm in the world?

You know the Fibonacci numbers:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

Each number is the sum of the previous two. Let’s say the zeroth Fibonacci number is zero, so:

And let’s say you want to write some code to compute this function. How would you do it? Perhaps something like this? (Python code)

def fib_rec(n):
  assert n >= 0
  if n < 2: return n
  return fib_rec(n-2) + fib_rec(n-1)

This is a pretty popular algorithm, which can be found in dozens of places online. It is also a strong candidate for the title of Worst Algorithm in the World. It’s not just bad in the way that Bubble sort is a bad sorting algorithm; it’s bad in the way that Bogosort is a bad sorting algorithm.

I’m planning to write a few things about mazes.

I had planned a short series of long, interactive essays, but it seems clear that I won’t get round to finishing them if I do it like that, so I’m going to try writing a few shorter more self-contained blog posts and see if anyone is interested.

I started to think about mazes after reading Jamis Buck’s excellent series of posts, and found that mazes lead quite directly to some interesting mathematics and some remarkable algorithms. So I’d like to share some of that here.

To whet your appetite, here is an exhaustive list of the 3×3 weave mazes:

I may or may not do it all on this site. Ideally I would like to post some interactive demos, which isn’t possible here.