Just when you thought cows couldn't be any more awesome, new research has shown that they may have a sense of the Earth's magnetic poles, as they tend to prefer to face in a north-south direction.

And yes I fully admit that the quality of this blog is dropping. But it wasn't all that high to begin with, was it?

There seems to be a trend towards centralising larger amounts of personal data. For example right now you can use Google's services to store all your email, contacts, documents, newsgroup subscriptions, photos, and your calender.

These 'free' services are provided because they allow Google to sell targeted advertising placements to its real customers. But should we really trust Google with all that personal data? what if it were abused, or leaked, or what happens when the courts are able to force certain data to be disclosed?

This is one of several reasons I have for advocating more decentralisation, in order to counter the trend. I firmly believe that my data should remain on my computer alone, 'just in case'. I'm even going to move most of my email back to my webhosting provider and use Gmail less. Now of course, that may be less secure there than at Google (easier for some sysadmin to abuse and not get noticed), but at least it isn't being held indefinitely in a massive database, and sold on as a product to advertisers. More to the point, the messages will only stay on the server until next time I retrieve them through POP3 and delete the remote copies, meaning that the permanent copies reside on my computer alone, and placing me in control of them.

Likewise the data given away to social networking services is worrying. What's interesting is that people have started using these as an alternative to email, which is barely usable now thanks to spam. And the problem with that is that unlike email, these services are closed and proprietary, which would mean giving up control once more to large companies.

Before we had these, we had similar tools, like finger on Unix. Of course finger isn't searchable, which is one problem with decentralising: people like the convenience of being able to search for data, emails, people, etc.

Another aspect of this comes from DRM and similar efforts to control what can and can't be done with certain files. I'm not going to get into a long debate regarding music piracy, mostly because all of my music is paid for anyway. Right now there exist 3 digital copies of my whole collection, and I can make as many more as I like thanks to avoiding these sort of restrictions. I think that using open source software helps here, as DRM isn't exactly popular in the open source community.

Indeed I see Linux and other open source software as the perfect means of seizing back what is rightfully mine - my computer, and my data.

Throughout 2007 and 2008 I have been acquiring more and more taste for non-popular music, for want of a better description, or 'classical' in its more broad - and less correct - sense. I've always had a deep love for music, and after starting to listen to jazz a few years back, this was the inevitable next step; I'm working my way backwards through musical history, by the looks of it.

This all started in tandem with my attempts to start playing the piano again. I used to mess around on this instrument when I was younger, but never made a real attempt to be able to play it. The inspiration to do so came from listening to jazz, and also to certain rock music (Muse works in some lovely piano, some of which, as I was later to learn, being based on Rachmaninoff).

With this ambition under way I soon needed some real pieces to learn, and I started by attempting Erik Satie's Gnossiennes, which were the only suitable pieces I had heard at the time. In my simple and inaccurate personal taxonomy at the time, Satie was 'classical music'. As the piano study continued, I also explored some other music, mostly by browsing videos on Youtube. I focused on piano music, but curiosity would often lead me to some orchestral material as well.

Soon I had added Edvard Grieg, Sergei Rachmaninoff and Edward Elgar to my music collection. Yet it was only last week that I decided to learn something about the history behind this music (this merely being an interesting afterthought, as such learning is irrelevant to the enjoyment of the music itself). I knew from school music lessons that though it is often used as an umbrella term, the term 'classical' really refers to one of several periods in European art history. I had no idea where any composers fell in that scale, and so was amused to realise that most of this music I had been exploring is in fact not classical music at all: the four composers I've mentioned so far are all part of the romantic movement/era.

Romanticism was an artistic movement which began during the 18th century. It emphasised emotion and experience (of the art). Romantic music (as I understand) was a departure from the strong formal structure used in classical music. There was even some exchange with jazz near the end of the movement, with Rachmaninoff's 4th piano concerto including some jazz influences, and Rachmaninoff himself being a great fan of jazz pianist Art Tatum.

I've decided to follow the BBC Proms this summer, which is a great way for someone who knows very little of this music to hear a lot of it. I've already taken a liking to several more composers, some of whom I had never even heard of before, such as Sergei Prokofiev and Vaughan Williams. In addition to this there have been programmes for world music and English folk, and performances of recently composed works.

As for the piano, I've learnt some of Satie's Gnossiennes, but not all yet. I've been playing with a few other pieces but I've got a long way to go. When I can play jazz, I'll be happy.

Over the last couple of years I have started to realise (or learnt the hard way) a few things about the process of studying mathematics which have gone against the assumptions I held before starting university. Maths isn't my main subject of study, but it is a big part of it, and since I enjoy it, I also dedicate a fair bit of my own time studying it further.

First off, memorizing formulas is a waste of time. You may pass an exam that way, but it's far better in the long run to take the time to really understand the maths behind a formula. For example, I've been reviewing a lot of statistics recently, and for the first time I can recite the formulae for the binomial probability distribution. Not because I've memorised it after copying it out 1000 times, but because (also for the first time) I actually understand what it means and so can reconstruct it in my head easily. I was never very good at probability, and this is something I'm now trying to correct.

I think that distinction between rote memorization, and reconstruction, is important. For a lot of people it's difficult to memorize things in maths for long, and moreover, if the initial understanding isn't there to begin with, then it is simply a wasted effort.

For when you actually need a formula, there are whole books filled with them (as well as series expansions and the like). And the most common ones seem to be printed in the back of every textbook I've used.

Second, it seems that however much experience you have, stupid arithmetic and algebraic mistakes still happen. Yesterday I was doing exercises on differential equations, and got the wrong answer twice over before realising I had missed a subtraction.

Additionally, mental/paper arithmetic skills aren't as important as school teachers insist, although they do help to provide a stronger mental feel for mathematics, they can speed things up, and are handy for quickly seeing if a solution makes sense.

Third, what was once difficult will become trivially simple eventually. The more maths you learn and practice, the more your existing knowledge and skills strengthen. Very early in school I found it hard to learn all the steps for solving a quadratic equation, which seems about as simple as breathing now.

Finally, the textbooks sometimes get the answers wrong, but more often than not it's your mistake (as much as I like to try and blame it on the book...)

Does anyone else have something to add to the list?

So earlier today I needed to look up cumulative probabilities over a binomial distribution with n = 30... as you do. Problem was I couldn't find any tables online which went that far.

The obvious solution was to use a spreadsheet, which I did, and it even had the function in-built. But then I was curious as to how to actually write an algorithm for it. More specifically, how to write a fast algorithm to do it.

The binomial distribution is used in a situation in which there is some event which can have one of two outcomes. The event is usually termed a 'trial', and one of the outcomes is defined to be 'success' while the other is 'failure' (though the terminology shouldn't be taken too literally). A probability p is assigned to a successful outcome, and consequently, q = 1 - p is the probability of failure.

If a trial is repeated n times then we can ask the question "what is the probability of k successes out of those n trials?". To work this out, the following reasoning is used:

1. There is an event which has probability p of occurring. The chance of it happening k times in a row is p^k.
2. If that event does happen k times during n trials, then the probability that it doesn't happen in any of the remaining n-k trials is q^(n-k) where q = 1 - p.
3. During n trials there are many different ways of arranging the k successes. For example, they could all happen in a row, or they could happen alternately in-between failures. In total there are n! / (n-k)!k! ways/orderings in which k successes may be selected from n trials. We will write this as nCk (the binomial coefficient).

Putting that together we get:

Pr(K = k) = nCk * p^k * q^(n-k)

Now for a more interesting question: "what is the probability that there are at most k successes?".

The solution is to add together the probabilities of 0 successes, 1 success, 2 successes, and so on, up to k successes, and this is called the cumulative probability. Naturally it would be far too tedious to calculate by hand, and that is where the computer program comes in handy.

As for the algorithm, it turns out (as can be expected) that computing nCk for each probability is what causes the most problems.

The most elegant way, in my opinion, of finding nCk is to use the following recursive function, where binom(n, c) is the same as nCk.

binom(n, 0) = 1
binom(n, n) = 1
nCn = binom(n - 1, k - 1) + binom(n - 1, k)

Which is based on Pascal's triangle. But though this looks very nice, it also becomes very slow for a computer as n - k gets larger.

Instead the solution used here is non-recursive and works by repeatedly doing a multiplication followed by a division. This is not only much faster than a recursive solution but avoids overflow by keeping the intermediate result small.

The source code is available here.

Following the release of Firefox 3, Microsoft sent Mozilla a cake to congratulate them. Isn't that nice of them? I'm pretty sure Microsoft didn't see any Firefox cake after IE 7 shipped.

I suppose it beats a giant IE logo on your lawn.

Another lazy posting lending itself to another quick riddle/logic problem...

You are at the bank of a river and, for some reason, you are travelling with one fox, one goat and one plant of unspecified species. While in your presence the fox and goat are very well-behaved, but if you ever leave the fox alone with the goat then the goat will be eaten. The same goes for the goat with the plant.

You have one boat and it can only carry you and one other item at a time. You obviously can't leave the fox and the goat on either side of the river unattended, and likewise you cannot leave the goat alone with the plant. Given all of this, how can you transport all three creatures and yourself to the other side safely?

I must also emphasize that the fox, goat and plant are your greatest friends, since you are a lonely traveller on a long journey. So I'm afraid you can't just abandon them and go on alone. Why would you have these particular creatures as your travelling companions? perhaps you went insane on your travels...

I have found a most excellent algorithm for calculating Fibonacci numbers. It's a beautiful algorithm, if I may say so, demanding only log(n) steps to find the nth number in the sequence.

I'll start by defining what I'm on about, for those who are confused. The Fibonacci sequence is a sequence of numbers where each number is the sum of the preceding two. We begin the sequence with the 1, 1...

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

Looking at the numbers in this sequence you will see that each value is the sum of the previous two values. The exception is the first two values, (1, 1). We define these values initially and the rest of the sequence grows from here.

We can describe the Fibonacci sequence nicely using the following recurrence relation:

fib(1) = 1;
fib(2) = 1;
fib(n) = fib(n – 1) + fib(n – 2);

It is a recursive definition. To find the n^th Fibonacci number we add together the n-1^th and the n-2^th - i.e. The previous two. Following that rule we will eventually hit both of the base cases, fib(1) and fib(2), which have been defined explicitly. The recursion ends at the base case.

Now programming this into a computer is quick and easy, and it is a very elegant description, but it is also a horribly inefficient method of calculating these numbers. Apart from the extensive use of stack space, it is also calculating all the intermediate values twice.

The number of operations performed for the first method grows exponentially in n – its exact complexity is O(φⁿ) where φ = (1 + sqrt(5)) / 2, the Golden Ratio.

A better method is an iterative one. We write an algorithm which looks something like this:

Integer fib(Integer n)

begin:

	Integer a := 1;

	Integer b := 0;

	for Integer i :=  1 to n

		//Compute next a, b values

		Integer next_a := a + b;

		Integer next_b := a;

		//Update – this really only needs on temporary variable but I used two for clarity

		a := next_a;

		b := next_b;

	next i



	return b;

end.

This is simple enough and significantly faster than the recursive algorithm. There are two assignments at the start, and each loop iteration consists of 4 assignments. So 2 + 4n operations, which comes to O(n).

Excellent, but can we improve on the linear algorithm? Well of course, otherwise I wouldn't be writing any of this in the first place. Some algebraic manipulation will provide us with a better algorithm:

The second algorithm applies the following mapping n times:

a <- a + b
b <- a

With an initial state (a, b) = (1, 0).

This mapping is a special case of a more general mapping, which we will call T_pq:

a <- bq + aq + ap
b <- bp + aq


Setting p = 0 and q = 1 we arrive at the above Fibonacci mapping. It can be shown that the result of T²_pq, that is, applying T_pq twice, is the same as applying T_p'q' once. This second mapping would give us every 2^nd pair of Fibonacci numbers, rather than every consecutive pair. If we can skip over some numbers while looking for the n^th Fibonacci number then we will certainly get there faster.

If p' and q' can be expressed in terms of p and q then we can build an algorithm which calculates a Fibonacci number by 'homing' in on the result. Jump some distance, then jump half that distance, and half again, until reaching the desired value.

And so here's the promised algebra... (transcribed from notes made yesterday)

1) Apply T_pq once

a = bq + aq + ap = q + p
b = bp + aq = q

(initial values a = 1, b = 0, were substituted in to produce the final expressions)

2) Apply T_pq again

a = q² + (q + p)q + (q + p)p = 2p² + 2pq + p²
b = qp + (q+p)q = pq + q² + pq = q² + 2pq

So these are the values of a and b after applying the mapping twice. Replace q with q' and p with p'

3) Solve for p' and q'

2p² + 2pq + p² = p' + q'
q² + 2pq = q'

Here I compare the result from mapping once using the values p' and q', with mapping twice using the values p and q. Then with some rearranging:

q' = q² + 2pq
p' = q² + p²

And that's the algebra over with. Now using p' and q', an algorithm is born...

Integer fib(n)

begin:

	//Set up initial state

	Integer a := 1;

	Integer b := 0;

	Integer p := 0;

	Integer q := 1;

	Integer nc := c;



	while(nc > 0)

		nc := nc / 2; //Discarding any fractional part

		Integer next_q := q*q + 2*p*q;

		Integer next_p := q*q + p*p;

		q := next_q;

		p := next_p;



		if nc is odd then

			Integer next_a := b*q + a*q + a*p;

			Integer next_b := b*p + q*q;

			a := next_a;

			b := next_b;

		end if

	repeat



	//Return result

	if(n is even)

		return b;

	else

		return a;	

end.

A couple of notes: when n is divided by two only the integer part should be kept. Secondly, notice that the loop results in a pair of integers (a, b). Which one we return as the result depends on whether the input, n, is even or odd.

We have 5 assignments before the loop. The loop itself will repeat until n is equal to zero, and n is repeatedly divided by two on each iteration of the loop. The number of times the loop repeats is thus given by log₂ n, or intuitively, the number of times we can divide n by two before it n becomes zero. We have 5 + log₂ n operations, giving a time complexity of O( log₂ n).

Now to give credit where it is due, I got the idea from this from exercise 1.19 in The Structure and Interpretation of Computer Programs – a book every computer scientist should read. The exercise is to find p' and q' in terms of p and q, which is what I showed above. I have written an implementation in c (Source code is here). The book has a nice lisp implementation of a similar algorithm.

Time for another post... just to show off another fractal image. I've been experimenting with full-colour rendering, but my colouring algorithm is still giving odd results. Still, I like this:

Most people have seen and heard of fractals, and even those who are not interested in the mathematics behind fractals still find them to be beautiful things to look at.

A fractal is a shape which exhibit self-similarity - that is, the shape is repeated within itself infinitely. There are many fractal-like structures in nature (minus the infinite recursion), including coastlines, trees, leaves and clouds.

Possibly the most famous kinds of fractals are the Julia and Mandelbrot sets. Here I will focus on the Julia set, and intend to cover the Mandelbrot in a future post. In both cases we are working in the complex plane, which is a space onto which the real and imaginary components of a complex number may be mapped. Real values are measured along the horizontal axis and imaginary values along the vertical. So the complex number c = 3 + 2i is represented with the coordinates (3, 2) on the complex plane.



Now for two complex numbers z and c consider the mapping

z = z^2 + c

If given any constant c we perform this mapping for each z in the complex plain then the Julia set for c is the set of z values which diverge or escape to infinity under the mapping z = z^2 + c. We can say that a particular value of z has escaped if it goes outside of a chosen escape radius measured from the point of origin. Since c can be any complex number, there exists an endless variety of fractals which can be generated using this mapping.

We can of course visualise the Julia set by using a simple algorithm:

for each point z in the plain
{
z = z^2 + c
if |z| > escape radius then paint that point black
otherwise, if we have reached the iteration limit, paint it white
}

The black points are those which are in the set. The algorithm must also count how many times the mapping has been applied, so that once this counter reaches a set limit, it can decide that the point is not a member of the set and paint it white.

To make things more interesting still we can use the number of iterations it takes before a point diverges to determine the colour or shade of that point.

What's amazing about this is the vast complexity which arises out of a very simple formula. Equally amazing is how changing the value of c even a little bit will often cause a dramatic change in the result (this is idea on which chaos theory is based). Here are some examples which I have rendered on a program I wrote last week in Java. I will be releasing the program and source here soon but first I need to make it more 'user friendly'. If I have the time I'd like to rewrite it in c++ to compare the rendering speeds too.


A well known Julia fractal which is meant to look like a rabbit


Rendering in multiple colours. Rotated 90 degrees from original output.


My favourite so far. Rendered with intensities of green determined by iteration count.

I mentioned self-similarity at the start of this post. If you were to zoom into a section from the edge of any Julia fractal then you will find the entire fractal repeated. Hanging on the edges of this repetition are yet more, smaller, repetitions...

I'm reasonably convinced that the world we experience is illusory. The seriousness with which I say this depends on my mood. If I'm feeling sensible then I mean it metaphorically, and refer to the way we like to project our desires, expectations and preconceptions onto the world, which distorts our perception of reality, leaving us woefully out of touch with it. But in my more extreme moments of madness I do literally mean the world is a simulation or dream of some sort... more on this at the end, but first, I have an apparent non-sequitur:

Déjà vu, French for 'already seen', refers to a collection of related psychological/neurological - and some would argue supernatural - phenomena. In general it is the feeling that one has experienced something before. These occur randomly and I suspect almost everybody experiences them. A person will often believe they have dreamt of the experience before, or are 'remembering the future'. Another folk explanation is that of past life memories.

One of the most popular scientific explanations is that there is a momentary delay in signal coming from one eye, so the brain processes the same data twice, which gives the person an eerie sense of familiarity. Another explanation is that some stimulus caused a related memory to be activated and the sense of familiarity is misinterpreted as having experienced the event before.

I can only speak for my own experience in describing déjà vu. When it happens it will last only about 10 or 20 seconds, but is followed by a strange feeling afterwards, presumably as the brain recovers from the confusion. During the experience I am overwhelmed by the incredulity of it - I'm absolutely certain I've had the experience before, but more certain that this is impossible. The problem when I try to gather my thoughts and do an experiment. If I say to myself "okay, if you've seen this before then what happens next?", then of course I can't answer. In fact, the feeling is so short-lived that I don't really have time. I just feel like I'm an observer watching events unfold. I normally laugh afterwards at how silly both myself and reality are.

When I was a child I would attribute these to remembering dreams. I was comfortable with the idea that I was dreaming of the future, but it always bothered me that I never remembered any of these 'dreams' until right after the moment they 'happened' in reality. My challenge to anyone who really believes they have precognitive dreams is this: start writing down your dreams every day. When you 'see it again', look back at your records for the original dream - bet you can't find it. Of course one can point out that most dreams are forgotten upon waking, but the exercise of writing them down will improve recollection in any case, so the experiment is still valid.

Another similar phenomenon is 'knowing' what someone is about to say in advance. Now this happened to me at least twice as a child. I have no explanation for them, and I'm fairly sure the context of the conversations didn't give any clues. However at a guess I would say such experiences are down to a combination knowing the other person well, non-verbal communication, and luck.

So I'm being very rational about these things. Dismissing them as mental illusions. However there is the other possibility - perhaps reality is an illusion, and these experiences, in addition to supposed psychic abilities, clairvoyance, are signs of flaws in the simulated world we inhabit. So is it our mind imposing illusions on the world, or the world imposing illusions on our minds? (and incidentally, is Chuang Chou a butterfly or a man?).

It is an interesting thought. Unfortunately it is not one which can be scientifically evaluated. It would lead to conclusion that since science is based on empirical observation, its validity may only apply to the false world in which those observations are made. So long as the false world is consistent, we may never notice, so this wouldn't matter to us, but it does mean that speculation about whether or not this world is real would be just that - idle speculation with no supporting evidence. This speculation is the same as speculation about the metaphysical and supernatural - interesting, but probably useless.

It is interesting how willing even the most intelligent people are willing to resort to magical and supernatural explanations for certain 'cognitive errors'. The problem is that when we experience something first hand, even if it doesn't match our normal experience of reality, it 'feels' equally real. In any case choose your reality well. The human brain is both a great tool for discovering how the universe works, but also a great deceiver.

Let's try five randomly* chosen words, and put them in Google:

Diffraction
Nucleation
Zen
Philosophy
Cheese

The first two lead to Wikipedia articles in the first result. In the case of 'zen', a Wikipedia article is on 3rd place, and there is one in 2nd place for 'philosophy', and likewise for 'cheese'.

Now I was planning to make the point that Wikipedia articles seem to dominate Google's search results now. Anything I search for seems to give a Wikipedia article as the first or second result. Not only does Wikipedia rank high in all these tests, for both 'philosophy' and 'zen', the first result is irrelevant. 'philosophy' is a skin care product, and 'zen' is an Internet Service Provider. The only one for which the first result is relevant and not a Wikipedia article, is cheese, where the first result links to a useful website dedicated to the subject and object of cheese.

What's my point? Wikipedia has a near monopoly on information now. I don't know if that's a good thing or not, but certainly Google's search results will appear to be of lower quality if Wikipedia is in nearly all of them.

*I am the random word generator, and I am satisfiably random.

Imagine you live in a country with a huge mail security problem: any package you send by postal mail will almost certainly have its contents stolen. However to protect a package you may put a padlock on it, and this will guarantee safe delivery.

Now imagine you want to send a present to a friend and don't want it to be stolen. You could put a padlock on your package, but then the recipient won't be able to open it, and you can't send the key either because they won't be able to get it out of the locked package. Assuming you haven't arranged something with your friend in advance (such as giving them a key in person), how can you get the present to them securely?

A kind note to Westerners:

Contrary to some popular beliefs, the founder of buddhism, Sidhartha Guatama (i.e. "The Buddha"), was not particularly fat. In fact it is most likely he was skinnier than me, as he was an ascetic for much of his life. For example, here is an image from Wikipedia:


(source)

That is a statue of the man buddhists refer to when they speak of the Buddha. So what about this?


(source)

This is a statue of a Chinese buddhist monk called, confusingly, budai (布袋 - not linguistically related to the Sanskrit word 'buddha' as far as I know), or hotei in Japanese. He is also commonly known as "the happy buddha" or "laughing buddha", where in this case, 'buddha' is used in the general sense refering to any enlightened being, rather than The Buddha, which refers to Siddhartha Guatama specifically. This monk is revered in certain predominantly buddhist countries including China and Thailand (the photo above is from a Thai temple).

Now for a story...

One day another monk happens upon Budai and asks him "what is zen?". Budai, saying nothing, drops his sack. The monk then asks him "what is the realization of zen?", and Budai picks up his sack again and continues on his way.

IBM has given me access to a mainframe and allowed me to mess around with it...

That is to say that I'm taking part in the IBM mainframe contest, a scheme intended to encourage students to gain experience with operating mainframes with obscure operating systems (z/OS).

The idea is to learn the operating system and file system and do some programming. There are tasks to complete and prizes for the first to complete them.

The first 200 to complete stage 1 win a t-shirt... it's taken me about 2 hours to complete stage 1, but I may be too late as I started this evening (the competition opened today). Anyone who makes it to stage 3 (the top 50 from stage 2) gets to actually go to IBM and do various fun things. I doubt I'll make it this far simply because I probably won't complete stage 2 in time - I've 4 uni assignments on the go right now.

Still it's fun to play with a mainframe.