Tuesday, July 21, 2009

Slow Papers are Frustrating

Three of the four papers I'm taking at university this trimester are so frustrating because they are going so slow. The offending papers are STAT131, COMP202 and COMP206. These three are admittedly all below the year of papers I should be taking, being a third year student (4 majors = falling behind in some courses), but still.

STAT131, being a paper full of first years probably has the best excuse out of these three, and the slowness is most likely exacerbated by the fact I've done second year maths, and one third year maths paper (doing another now), but the lecturer spends so much time explaining things, and going over things more times than he has to. We've had 4 lectures now, and only covered like 12 pages of the student notes. It's around 150 pages (remarkably short) and we have 30 lectures, so we should at least be up to page 20. Ah well, it's probably my fight for going to lectures. I skipped the tutorial today because the assignment was so ridiculously easy.

COMP206 is the one that causes me the most frustration. We spent like 15 minutes in one lecture going over function calls. When every student there has had to have done two papers in Java (as they're prerequisites) they must know how these work. And with programming, you can only do so much in lectures, they should only be going over the language features very briefly, and then let us learn all the ins and outs by writing actual code, at least to me. Instead they covering things in way too much detail in the lectures, and the assignment we got (due in 2 weeks time) was crazily short, I finished it in 2 hours and did more than I had to do.

COMP202 isn't so bad, we're not really going over the stuff particularly slowly, but there are other reasons why the lectures of this paper frustrate me. Firstly, way too many people talk in the lectures, come on, this is university guys. And when our (current) lecturer doesn't talk that loudly (plenty loud enough when people aren't talking) it makes for quite an infuriating time. Also, out lecturer is a little too nice, when people ask questions that really should be done in a tutorial, helpdesk, email, on the forum or whatever, she'll stop and help them for 5 minutes when it doesn't really relate to what we're doing and is of little help to the other people in the theatre. Especially as it is a rather difficult setting to answer one on one questions well, so they don't often get answered satisfactorily for the asker.

Ah well, my only hope is these papers get better as time goes on (and possibly as lecturers change). Enough of a rant by me.

RIP Marcoland

One week ago, the game I had been playing for a ridiculously long time went the way of the moa. I signed up to Marcoland back in 05, when I was in Japan, in November if I remember rightly. That's 3 and a half years ago - about a sixth of my life, crazy to think I played it for so long. In that time it was one of the things I'd do on the Internet every day, and I would hate to think the amount of time I spent there.

It was a MMORPG (Massively Multiplayer Online Role-Playing Game), you spent your time increasing your stats. There were also towns (the ML version of clans/guilds/etc), which would have wars with each other, a daily arena, a pvp system, and a whole bunch of other things. But, as with virtually all games of this type it got pretty repetitive, and if it hadn't been for the community there, in towns, in chat, in the forums, I'm sure I would've left a lot sooner. It was one of those games where you could play it in 5 minutes, or spend however much longer than that you wanted to there. And it was completely free, you couldn't get any advantages by donating (just nice things like a coloured name, an avatar, no ads, a custom emoticon, etc).

It's weird to think that it's gone, but I'm fairly sure it won't be back, at least not permanently that is. I've been finding I have a lot more free time so it's probably a good thing. I'd thought about quitting for a while for that very reason. I remember the day the site went down, a week ago now, I got on my computer, finished doing the other things I do on the net, and then was like, what do I do now?

I quite enjoyed the game though, it appealed to me in a number of ways. Firstly, it was a long term game, it involved a lot of planning. It also gave you a lot of stats, which I always like going through. I even programmed a few things for it, like a simulator to simulate the training beach to figure out what monster would be best to fight, a town war visualiser thing (which I never finished) and a little script-like thing that would parse the rankings pages to list players with the most protection.

The in game chat room was almost certainly the place I wasted the most time. I didn't start using this until I had been playing for about a year (or so, can't remember exactly), but I spent so much time there. Met a bunch of people - who I'll sadly lose contact with now. I had something like 80,000 chat lines I think. Which is sick. All that time lost. I was even a chat mod for a few months before the end.

I was pretty strong as a player goes, about 100th in terms of total stats, and about 30th in terms of stats/age (which gave a fairer reflection of how well younger players were doing). I would've been better than this but I didn't play so well at first, but I made up a lot later.

So would it have been better if I had never started playing? I reckon no. All in all I reckon the time I spent playing was a positive. It helped me out I reckon, and there'll be people I'll try to not lose contact with. It was something that was always with me, and would often cheer me up when I wasn't feeling so great. I don't want to play another similar game though, because I know how much time it takes, and would prefer to spend the time studying, or out in the world with friends, or whatever.

Anywho, good bye Marcoland, you were good while you lasted. And thanks Marco, thanks for all you gave to the players of ML.

Saturday, July 18, 2009

String Permutations II

I thought of a few ways I could optimise the permutation routines from yesterday, which were relatively simple, so I thought I'd try them out. I'm always interested in ways I can make code faster, and enjoy testing things like this out. Most of the improvements this time round were to the iterative method:
 1: public static List<String> getAllPermutationsIteratively(String s) {
 2:    int length = s.length();
 3:    if(length <= 1) {
 4:       return Arrays.asList(s);
 5:    }
 6: 
 7:    int numPermutations = factorial(length);
 8: 
 9:    List<String> permutations = new ArrayList<String>(numPermutations);
10: 
11:    for(int permNo = 0; permNo < numPermutations; permNo += 2) {
12:       char[] charsLeft = s.toCharArray();
13:       
14:       int size = length;
15:       
16:       char[] charArray = new char[length];
17:       
18:       int i, factorialSize = factorial(size);
19:       for(i = 0; i < length - 2; i++) {
20:          // The division means that the index only increases after so many iterations
21:          // The remainder reduces the number range to the number of iterations the index stayed
22:          // the same for in the previous division
23:          int factorialSizeMinusOne = factorial(--size);
24:          int index = (permNo % factorialSize) / factorialSizeMinusOne;
25:          factorialSize = factorialSizeMinusOne;
26:          
27:          charArray[i] = charsLeft[index];
28:          
29:          // Copy all elements from (index+1) onwards back one place, i.e. remove the element at
30:          // index. Note that size was decremented earlier.
31:          System.arraycopy(charsLeft, index+1, charsLeft, index, size - index);
32:       }
33:       
34:       charArray[i] = charsLeft[0];
35:       charArray[i + 1] = charsLeft[1];
36:       permutations.add(new String(charArray));
37: 
38:       charArray[i] = charsLeft[1];
39:       charArray[i + 1] = charsLeft[0];
40:       permutations.add(new String(charArray));
41:    }
42:    return permutations;
43: }
I got a new source code to html formatter by the way which I think gives better results. The first change isn't for performance, but just ensures it works properly for strings of length 0 (they could just as well throw an exception) and 1, which would've worked in my old iterative version, but not in my old recursive version (I think).

Next, I changed the loop so it increments by two each time, and did the final two letters e.g. AB and BA manually, which was a big performance improvement. The next one was saving the calculated factorial values, which saves one factorial calculation through iteration of the inner loop, which is again nice. I tried various ways of making this faster, but couldn't make it faster than it is here. Then instead of using an ArrayList of Characters, I changed it to use an array of chars, which performs better, but is a little trickier. This brought the speed of this version to be roughly equivalent to the recursive version.

Now I changed the recursive version to:
 1: public static List<String> getAllPermutationsRecursively(String s) {
 2:    int length = s.length();
 3:    if(length <= 1) {
 4:       return Arrays.asList(s);
 5:    }
 6: 
 7:    List<String> permutations = new ArrayList<String>(factorial(length));
 8: 
 9:    char[][] charArray = getAllPermutationsRecursively(s.toCharArray(), length, length - 1);
10:    for(int i = 0; i < charArray.length; i++) {
11:       permutations.add(new String(charArray[i]));
12:       charArray[i] = null; // Let the gc be able to clear this up
13:    }
14: 
15:    return permutations;
16: }
17: 
18: // length is the length if the original String
19: // pos is the current position in the char[] which a character will be added to. On the first
20: // call of this it should be one less than length
21: private static char[][] getAllPermutationsRecursively(char[] chars, int length, int pos) {
22:    char[][] toReturn = new char[factorial(pos + 1)][];
23: 
24:    // Though the == 1 case is simpler, it's faster if this is the base case
25:    if(chars.length == 2) {
26:       // There are two combinations, [0, 1] and [1, 0]
27:       toReturn[0] = new char[length];
28:       toReturn[1] = new char[length];
29: 
30:       toReturn[0][0] = toReturn[1][1] = chars[1];
31:       toReturn[0][1] = toReturn[1][0] = chars[0];
32:    } else {
33:       int toReturnPos = 0;
34:       for(int i = 0; i < chars.length; i++) {
35:          char c = chars[i]; // The current char
36: 
37:          // Make a copy of the array without c in it
38:          char[] newChars = new char[chars.length - 1];
39:          System.arraycopy(chars, 0, newChars, 0, i);
40:          System.arraycopy(chars, i + 1, newChars, i, chars.length - i - 1);
41: 
42:          // Add c to each of the returned arrays of chars
43:          for(char[] charArray : getAllPermutationsRecursively(newChars, length, pos - 1)) {
44:             charArray[pos] = c;
45:             toReturn[toReturnPos++] = charArray;
46:          }
47:       }
48:    }
49:    return toReturn;
50: }
This one only has a couple of minor changes, nothing major, it seems I did it pretty well the first time.

While doing this process I burnt my fingers a little with relatively shoddy benchmarking. At first I was getting wildly erratic results, even though I would run each version say 5 times, the time would vary by 50% (or more) between runs, which I thought was pretty crazy. The first thing I thought of doing to combat this was set my cpu governor to performance rather than dynamic, which means that it'll sit at full speed all the time, rather than throttling down. This made a remarkable difference, it seems there was a bit of lag in it going to full speed. I also have backround programs running, which you shouldn't really, but as I only run this in one thread, it shouldn't make too much of a difference.

The second main thing was that the JVM wasn't getting enough memory, so the one running second would run slower as the gc would run a lot more. By setting the starting and finishing memory to 512 MB (more than it should need, but I wanted to be on the safe size), I eliminated this discrepancy to a large degree. This also speed up the speed of execution by as much as two times, which is pretty remarkable. What brought this to my attention was running on "PARTICLEX" it would crash with an out of memory error when I changed the code and ran the iterative version first. It must've been right on the cusp of running out of memory before.

For a bit of analysis - the performance of the two in terms of speed is very close now. However in terms of memory, the iterative version should use less, but after the couple of changes I made to the recursive one that shouldn't be too bad. The iterative version is slightly shorter, so would probably get a slight preference by me, but hey. (Not that I can see any practical purpose for this).

Friday, July 17, 2009

String Permutations

Apparently the "Challenge" in the COMP102 assignment was to write some code to print out all the permutations of a string. (Say for ABC, that'd be ABC, ACB, BAC, BCA, CAB, CBA). However that challenge was apparently left over from last year, and due to the number of points of the paper changing, they haven't covered recursion yet. So I got challenged by a friend to write a program that did this without using recursion (which is the natural way I would do it).

I puzzled over this for a while, trying a couple of ways, with little success. Then I went to a tutorial for another paper, but didn't really pay much attention, more trying to figure out a solution for this problem. I made a little bit of progress, but the solution I implemented when I got back to the lab didn't work. But then I had a bit of a brain wave as I was working and managed to do it. Here's the code:
  1: public static List<String> getAllPermutationsIteratively(String s) {
  2:    int length = s.length();

  4:    List<Character> chars = new ArrayList<Character>(length);
  5:    for(char c : s.toCharArray()) {
  6:       chars.add(c);
  7:    }

  9:    int numPermutations = factorial(length);

 11:    List<String> permutations = new ArrayList<String>(numPermutations);

 13:    for(int permNo = 0; permNo < numPermutations; permNo++) {
 14:       List<Character> charsLeft = new ArrayList<Character>(chars);

 16:       char[] currentString = new char[length];

 18:       for(int i = 0; i < length; i++) {
 19:          int index = (permNo % factorial(charsLeft.size())) / factorial(charsLeft.size() - 1);
 20:          currentString[i] = charsLeft.remove(index);
 21:       }

 23:       permutations.add(new String(currentString));
 24:    }
 25:    return permutations;
 26: }
Line 19 contains the magic statement. I commented this as, "The division means that the index only increases after so many iterations. The remainder reduces the number range to the number of iterations the index stayed the same for in the previous division." I don't know if that helps all that much, but if you write down a table (which I can't be bothered doing) it makes a lot more sense what's happening. (Or get it to process "0123" or "01234" and print out each string in the resulting list)

I then wondered how this would compare to a recursive implementation, so did one of those too:
  1: public static List<String> getAllPermutationsRecursively(String s) {
  2:    int length = s.length();

  4:    List<String> permutations = new ArrayList<String>(factorial(length));

  6:    for(char[] c : getAllPermutationsRecursively(s.toCharArray(), length, length - 1)) {
  7:       permutations.add(new String(c));
  8:    }

 10:    return permutations;
 11: }

 13: private static char[][] getAllPermutationsRecursively(char[] chars, int length, int pos) {
 14:    char[][] toReturn = new char[factorial(pos + 1)][];

 16:    if(chars.length == 2) {
 17:       toReturn[0] = new char[length];
 18:       toReturn[1] = new char[length];

 20:       toReturn[0][0] = toReturn[1][1] = chars[1];
 21:       toReturn[0][1] = toReturn[1][0] = chars[0];
 22:    } else {
 23:       int toReturnPos = 0;
 24:       for(int i = 0; i < chars.length; i++) {
 25:          char c = chars[i];

 27:          char[] newChars = new char[chars.length - 1];
 28:          System.arraycopy(chars, 0, newChars, 0, i);
 29:          System.arraycopy(chars, i + 1, newChars, i, chars.length - i - 1);

 31:          for(char[] charArray : getAllPermutationsRecursively(newChars, length, pos - 1)) {
 32:             charArray[pos] = c;
 33:             toReturn[toReturnPos++] = charArray;
 34:          }
 35:       }
 36:    }
 37:    return toReturn;
 38: }
Despite this being a little longer, conceptually I think it's much simpler. (Yes, I did strip out the comments to be annoying). It's not the first version I wrote, but rather as optimised as I could be bothered doing, making it much faster than my original naive implementation.

This version turns out to be more than twice as fast as the iterative version. The two main reasons for this are that the iterative version copies, then removes the elements of a List copy of the chars in the string for every string returned, and it also does a whole lot of remainder and division operations.

Oh yeah, if you're wondering this is my factorial function:
  1: private static int factorial(int n) {
  2:    int factorial = 1;
  3:    for(int i = 2; i <= n; i++) {
  4:       factorial *= i;
  5:    }
  6:    return factorial;
  7: }
I tried a few versions, including saving each value to a list, then an array so they wouldn't have to be calculated again, and having the first 10 values precalculated, but these were slower, so I went back to this implementation. It's probably got something to do with the way the compiler optimises it.

The other thing to note with this implementation is that there is a maximum length for the string. Say the length of the input string is n, then n! must be less than 2^31 (the maximum value of an int) otherwise the arrays cannot be made big enough to fit all the permuatations. This means you can use words at most 12 letters long. In practice, I only got it to work for strings of length 10 or less. I ran out of stack space, even when allocating 2500 MB for a 11 letter word. It wouldn't let me set the memory to 3000 MB or higher for some reason.

This shows I'm up to the COMP102 challenge. Boy is that satisfying.

Consecutive Heads

In the extremely advanced statistics paper I'm doing (STAT131), our lecturer mentioned something about consecutive heads (or tails) on a coin toss. Saying that the series T, HT, HHT, HHHT, ... is theoretically infinite. Which is true. But in practice your sequence of heads is going to be relatively short.

To prove this I wrote a little Java program that would calculate these chains using the built-in pseudorandom number generator. After I got this working, I ran it for an hour on one of the uni computers. For the 80 billion trials it did, the longest chain was only 36. That's pretty short really. (I don't think the non-randomness of the pseudorandom number generator would've had any significant effect). Evaluate 2^36 and you get 70 billion (to 1 significant figure), so this was basically as expected, a chain of length 36 is a one in 70 billion chance. That's a (relatively) huge number really.

Just for fun I reimplemented my program in C, which made it about 20% faster, which is about what I expected. (Actually, it was slower on a multicore computer as I multithreaded the Java version, but I don't know how to write threaded programs in C). Anyways, that was my interesting experiment for Tuesday (when I did it).

Tuesday, July 14, 2009

Bah, fitness

So, yesterday was my first day back at uni, for about a month when you take into account holidays and the study break. It seems I lost some of my fitness in the downtime, because when I was running for the train in the morning, I got tired much earlier than I remember doing at the end of the last trimester. Running for the train is how I stay fit, a lot of the time, even if I'm not running late (everyone loves a bad pun don't they), I'll still run because I enjoy it. However I never seem to be motivated to spontaneously go for a run during my down time.

But I like being fit, to at least some degree, so I really need to try and actually do some exercise in the holidays. Hopefully it'll be easier over Summer, when it's a bit warmer, which is my next long break. I did take up press ups (push ups? I never know which is right, or even if one is more correct than the other), and I try and rattle off 20-30 of these every now and again. Sometimes I try and exercise other muscles, such as doing squats or crunches, but am usually too lazy to do these. Running and press ups alone are pretty good though, I reckon. I would also like to do pull ups, but don't have anywhere to do them really, I don't really like doing things like this in public, because it feels like I'm showing off, and I generally suck at first.

Sunday, July 12, 2009

Holidays always seem so short...

I'm going back to university tomorrow, but it feels like the holidays have only just begun. Admittedly I did have a rather short holiday this time, a week and a half due to having an exam on the last day of exams, when they're normally at least 2 weeks, but surely they're supposed to feel longer than this?

It's not such a bad thing I suppose, being back at university has it's advantages, but everyone likes holidays, having nothing you _have_ to do all day is so nice, and no nagging feeling that you should be studying.

In retrospect these holidays have been pretty good, had the snow camp in the one weekend enclosed in holidays, though it would've been nicer if it had been a little longer. Got a significant amount of work done on my game, caught up on a bunch of sleep, and just blobbed in general doing a few other things, but it would've been nice if it had gone on a little longer.

I do have a much nicer timetable this term compared to the last. At the moment (before any labs or tuts), I start an hour later on mon, tue, thu, and fri, and finish an hour earlier every day. I do have class at 12 on mondays which means I won't be able to make it to the Kohanga liturgy which isn't cool, but these things happen. Anywho, lets see how the next trimester goes.

Saturday, July 11, 2009

Grrr... blog issues

I just had some annoying blog issues when making that last entry.

Firstly, not all my bits of LaTeX code would show, I think it's because some of them were too long. So I made my own images and uploaded them. That's why some of the images look a little different to the others (I reckon they look better as they seem to have better anti-alisaing.

Secondly, to try and solve the above problem, and the fact that a number of the images were too wide for my blog, I started hacking at the template. Since some of the backgrounds were images, I had to download them and make them wider for myself. Blogger uses picasa by default for images, which is really annoying for getting a direct link, normal size, to an image, and it doesn't seem to have any regular way of providing the links, there seem to be almost random character combinations in the url. So I gave up on this and as you can see, I don't use images in the background of the main areas (there still are a few images in other places, but I think I'll keep them). I did get the template working alright though, it'll probably change some more in the near future.

By default, blogger automatically puts html breaks in where you have line breaks in the input area. This was messing me up a little so I turned this off. Blogger then goes and decides to apply this retrospectively, breaking all my previous posts so I had to go and fix them, lucky this blog is pretty new and there were less than 30... I think this way will be an improvement for the future though, it gives me more flexibility when writing and lets me practise my html more.

Grrr...

Friday, July 10, 2009

Solving the Schrödinger equation for the hydrogen atom

When I was studying for my quantum physics exam on Wednesday before last, this struck me as very elegant, albeit rather long and difficult. I had worked through it by hand, as I like doing that when I study as just reading doesn't make things sink into my brain, so I thought I'd put these notes up here, for anyone who's interested (plus, I like playing in LaTeX).

Think of when this was first done, Schrödinger was trying to see if his equation would fit in with observed phenomena, things known at the time, so he initially solved it for the hydrogen atom, which was known. Not any of these infinite square wells, harmonic oscillators, etc. you start with nowadays, as only recently have we become able to observed the effects of these.

So prepare yourself for a whole lot of maths, with a little physics woven in between.

Time-independent Schrödinger equation in spherical coordinates

So we start off with the time-independent Schrödinger equation (in 3D):

$$ - \frac{\hbar^2}{2m} \nabla^2 \psi + V \psi = E \psi$$

In spherical coordinates, the Laplacian becomes (according to wikipedia (therefore true) and other places):

$$ \nabla^2 = \frac{1}{r^2} \frac{\partial}{\partial r} \left( r^2 \frac{\partial}{\partial r} \right) + \frac{1}{r^2 \sin \theta} \frac{\partial}{\partial \theta} \left( \sin \theta \frac{\partial}{\partial \theta} \right) + \frac{1}{r^2 \sin^2 \theta} \left( \frac{\partial^2}{\partial \phi^2} \right)$$

Thus the time-independent Schrödinger equation becomes:


First, look for separable solutions of the form $$ \psi \left( r, \theta, \phi \right) = R \left( r \right) Y \left( \theta, \phi \right)$$, which gives:

equation

Now, if the potential, $$ V$$ only depends on $$ r$$ then the first of these square brackets only depends on $$ r$$ and the second only depends on $$ \theta$$ and $$ \phi$$. Thus they must both be equal to a constant, lets call this $$ l \left( l + 1 \right)$$ (because I like being difficult), so:

$$\begin{aligned} \frac{1}{R} \frac{d}{d r} \left( r^2 \frac{d R}{d r} \right) - \frac{2mr^2}{\hbar^2} \left( V - E \right) &= l \left( l + 1 \right)\\ \frac{1}{Y} \left[ \frac{1}{\sin \theta} \frac{\partial}{\partial \theta} \left( \sin \theta \frac{\partial Y}{\partial \theta} \right) + \frac{1}{\sin^2 \theta} \left( \frac{\partial^2 Y}{\partial \phi^2} \right) \right] &= -l \left( l + 1 \right)\end{aligned}$$

The Radial Equation

The first of the above two equations can be simplified by letting $$ u \left( r \right) = r R \left( r \right) $$. Now:

$$\begin{aligned} \frac{du}{dr} &= R + r \frac{dR}{dr} \\ \mathrm{and\ so\quad} \frac{dR}{dr} &= \frac{\frac{du}{dr} - R}{r} = \frac{\frac{du}{dr} - \frac{u}{r}}{r} = \frac{r \frac{du}{dr} - u}{r^2} \\ \mathrm{thus\quad} \frac{d}{d r} \left( r^2 \frac{d R}{d r} \right) &= \frac{d}{d r} \left( r \frac{du}{dr} - u \right)\\ &= \frac{du}{dr} + r \frac{d^2 u}{dr^2} - \frac{du}{dr}\\ &= r \frac{d^2 u}{dr^2}\end{aligned}$$

Now subbing into the earlier equation:

$$\begin{aligned} \frac{1}{R} \frac{d}{d r} \left( r^2 \frac{d R}{d r} \right) - \frac{2mr^2}{\hbar^2} \left( V - E \right) &= l \left( l + 1 \right)\\ \frac{r}{u} r \frac{d^2 u}{dr^2} - \frac{2mr^2}{\hbar^2} \left( V - E \right) &= l \left( l + 1 \right)\\ \frac{d^2 u}{dr^2} - \frac{2m}{\hbar^2} u \left( V - E \right) &= \frac{l \left( l + 1 \right)u}{r^2}\\ \frac{\hbar^2}{2m} \frac{d^2 u}{dr^2} - u \left( V - E \right) &= \frac{\hbar^2}{2m} \frac{l \left( l + 1 \right)u}{r^2}\\ - \frac{\hbar^2}{2m} \frac{d^2 u}{dr^2} + \left( V + \frac{\hbar^2}{2m} \frac{l \left( l + 1 \right)}{r^2} \right) u &= Eu \end{aligned}$$

That looks pretty familiar, doesn't it?

Hydrogen Atom

Now that the basis is there, we can actually start looking at stuff specific to the hydrogen atom. Firstly, the potential energy function is Coulomb's law:

$$ V \left( r \right) = - \frac{e^2}{4 \pi \varepsilon_0} \frac{1}{r}$$

Subbing this into the radial equation derived above gives:

$$ - \frac{\hbar^2}{2m} \frac{d^2 u}{dr^2} + \left( - \frac{e^2}{4 \pi \varepsilon_0} \frac{1}{r} + \frac{\hbar^2}{2m} \frac{l \left( l + 1 \right)}{r^2} \right) u = Eu$$

Now let $$ k = \frac{\sqrt{-2mE}}{h}$$, which is, of course, real as we're looking at the bound states, so $$ E < 0$$. Manipulating the radial equation gives:

$$\begin{aligned} - \frac{\hbar^2}{2mE} \frac{d^2 u}{dr^2} + \left( - \frac{e^2}{4 \pi \varepsilon_0} \frac{1}{r} \frac{1}{E} + \frac{\hbar^2}{2mE} \frac{l \left( l + 1 \right)}{r^2} \right) u &= u\\ \frac{1}{k^2} \frac{d^2 u}{dr^2} + \left( - \frac{e^2}{4 \pi \varepsilon_0} \frac{1}{r} \frac{1}{E} \frac{k^2}{k^2} - \frac{1}{k^2} \frac{l \left( l + 1 \right)}{r^2} \right) u &= u\\ \frac{1}{k^2} \frac{d^2 u}{dr^2} + \left( \frac{e^2}{4 \pi \varepsilon_0} \frac{1}{r} \frac{2m}{\hbar^2} \frac{1}{k^2} - \frac{1}{k^2} \frac{l \left( l + 1 \right)}{r^2} \right) u &= u\end{aligned}$$

$$ \frac{1}{k^2} \frac{d^2 u}{dr^2} = \left( 1 - \frac{m e^2}{2 \pi \varepsilon_0 \hbar^2} \frac{1}{r} \frac{1}{k^2} - \frac{1}{k^2} \frac{l \left( l + 1 \right)}{r^2} \right) u$$

This isn't looking very good, so lets try another substitution, $$ \rho = kr$$ and $$ \rho_0 = \frac{me^2}{2 \pi \varepsilon_0 \hbar^2 k}$$. With these, $$ \frac{d^2u}{dr^2} = \frac{d^2u}{d\rho^2} \frac{d^2\rho}{dr^2} = \frac{d^2u}{d\rho^2} \frac{1}{k^2}$$, so we get:

$$ \frac{d^2u}{d\rho^2} = \left(1 - \frac{\rho_0}{\rho} + \frac{l \left( l + 1 \right)}{\rho^2} \right) u$$

This looks a whole lot simpler, but is still not easy to solve. We'll try breaking off the behaviour of $$ r$$ and thus $$ \rho$$ tends to 0 and $$ +\infty$$.

$$ \lim_{\rho \to +\infty} \frac{d^2u}{d\rho^2} = u$$

with solution:

$$ u \left( \rho \right) = A e^{-\rho} + B e^{\rho}$$

and (assuming $$ l \neq 0$$):

$$ \lim_{\rho \to 0} \frac{d^2u}{d\rho^2} = \frac{l \left( l + 1 \right)}{\rho^2} u$$

Unlike the previous equation, the solution to this isn't well known (at least to me), but can be easily solved by the power series method. Propose a solution, $$ u = \sum_{n=-\infty}^{+\infty} a_n \rho^n $$. This has derivatives:

$$ \frac{du}{d\rho} = \sum_{n=-\infty}^{+\infty} n a_n \rho^{n-1} \quad \mathrm{and} \quad \frac{d^2u}{d\rho^2} = \sum_{n=-\infty}^{+\infty} n \left( n - 1 \right) a_n \rho^{n-2}$$

Subbing these into the differential equation gives:

$$\begin{aligned} \sum_{n=-\infty}^{+\infty} n \left( n - 1 \right) a_n \rho^{n-2} &= \frac{l \left( l + 1 \right)}{\rho^2} \sum_{n=-\infty}^{+\infty} a_n \rho^n \\ \sum_{n=-\infty}^{+\infty} n \left( n - 1 \right) a_n \rho^{n-2} &= l \left( l + 1 \right) \sum_{n=-\infty}^{+\infty} a_n \rho^{n-2}\end{aligned}$$

Which is only true when $$ n \left( n - 1 \right) = l \left( l + 1 \right) $$, $$ n = l + 1, -l $$. So all other $$ a_n$$ must be zero, giving the solution:

$$\begin{aligned} u \left( \rho \right) &= a_{l+1} \rho^{l + 1} + a_{-l} \rho^{-l} \\ &= C \rho^{l + 1} + D \rho^{-l}\end{aligned}$$

Now if you're anything like me, you'll want to double check this, so lets do that now:

$$\begin{aligned} \frac{du}{d\rho} &= \left(l+1\right) C \rho^l - l D \rho^{-l-1}\\ \frac{d^2u}{d\rho^2} &= l \left(l+1\right) C \rho^{l-1} - \left(-l-1\right) l D \rho^{-l-2}\\ &= l \left(l+1\right) \left( C \rho^{l-1} + D \rho^{-l-2} \right)\\ &= \frac{l \left(l+1\right)}{\rho^2} u\end{aligned}$$

So yep, this is a solution (well, family of solutions). However, as $$ r$$ and correspondingly $$ \rho$$ tends to zero, the second term tends to infinity, so $$ D$$ must be zero. So now combining these, we get:

$$ u \left( \rho \right) = \rho^{l+1} e^{-\rho} v \left( \rho \right)$$

In the hope that $$ v\left(\rho\right)$$ will be easier to solve than $$ u\left(\rho\right)$$. Now we want to get the radial equation in terms of $$ v$$ rather than $$ u$$. So first we'll find its derivatives:


And now subbing this into the radial equation:


Which isn't all too bad really, but is still not easy to solve. Again, lets go down the power series route, proposing a solution of the form $$ v \left( \rho \right) = \sum_{j=0}^{\infty} c_j p^j$$. The derivatives are:

$$ \frac{dv}{d\rho} = \sum_{j=0}^{\infty} j c_j \rho^{j-1} \quad \mathrm{and} \quad \frac{d^2v}{d\rho^2} = \sum_{j=0}^{\infty} j \left( j - 1 \right) c_j \rho^{j-2}$$

Subbing these in gives:


Now, by equating the coefficients of $$ \rho^j$$, we get:

$$\begin{aligned} j \left( j + 1 \right) c_{j+1} + 2 \left( l + 1 \right) \left( j + 1 \right) c_{j+1} - 2 j c_j + \left(\rho_0 - 2 \left(l+1\right) \right) c_j &= 0 \\ \left( j + 1 \right) \left[ j + 2 \left( l + 1 \right) \right] c_{j+1} - \left[ 2j - \rho_0 + 2 \left( l + 1 \right) \right] c_j &= 0\end{aligned}$$

Which gives the recurrence relation:

$$ c_{j+1} = \frac{ 2 \left( j + l + 1 \right) - \rho_0}{\left( j+1 \right) \left( j + 2l + 2 \right)} c_j$$

But at large $$ j$$ (and $$ \rho$$), $$ c_{j+1} = \frac{2j}{j \left( j+1 \right)} c_j = \frac{2}{j+1} c_j $$. Suppose this were the actual solution, then:

$$ c_j = \frac{2}{j} c_{j-1} = \frac{2}{j} \frac{2}{j-1} c_{j-2} = \cdots = \frac{2^j}{j!} c_0$$

And then:

$$ v \left( \rho \right) = c_0 \sum_{j=0}^{\infty} \frac{2^j}{j!} p^j = c_0 e^{2\rho}$$

By the power series definition of the exponential function. Hence:

$$\begin{aligned} u \left( \rho \right) &= \rho^{l+1} e^{-\rho} v \left( \rho \right) \\ &= c_0 \rho^{l+1} e^\rho\end{aligned}$$

Which goes to infinity as $$ \rho$$ (and thus $$ r$$) tends to infinity, which is not good. These are mathematical solutions to the equation, but are not normalisable so aren't physical solutions. Thus the series has to terminate somewhere, i.e. there must be some $$ j_{max}$$ such that $$ c_{j_{max} + 1} = 0$$ (and all later terms will also be zero be the recurrence relation). Thus, by going back to the recurrence relation:

$$ c_{j_{max}+1} = \frac{ 2 \left( j_{max} + l + 1 \right) - \rho_0}{\left( j_{max}+1 \right) \left( j_{max} + 2l + 2 \right)} c_{j_{max}} = 0$$

$$ 2 \left( j_{max} + l + 1 \right) - \rho_0 = 0$$

Now, lets define the principle (my textbook called this principal, but surely that's incorrect) quantum number, $$ n$$, to be $$ \left(j_{max} + l + 1\right)$$ and thus $$ \rho_0 = 2n$$. Now going way back, remember$$ k = \frac{\sqrt{-2mE}}{\hbar}$$,$$ \rho = kr$$ and$$ \rho_0 = \frac{me^2}{2 \pi \varepsilon_0 \hbar^2 k}$$. So

$$\begin{aligned} 2n &= \frac{me^2}{2 \pi \varepsilon_0 \hbar^2 k} \\ \frac{\sqrt{-2mE_n}}{\hbar} &= \frac{me^2}{4 \pi \varepsilon_0 \hbar^2 n} \\ -2mE_n &= \frac{m^2e^4}{16 \pi^2 \varepsilon_0^2 n^2 \hbar^2} \\ E_n &= - \frac{me^4}{32 \pi^2 \varepsilon_0^2 n^2 \hbar^2} \\ &= \frac{E_1}{n^2}\end{aligned}$$

These are the allowed energies of the electron, which were known before the Schrödinger equation was developed. Though it was formulated by Niels Bohr somewhat arbitrarily. Also, $$ k$$ can be nicely expressed in terms of the Bohr radius, $$ a_0 = \frac{4 \pi \varepsilon_0 \hbar^2}{me^2} = 0.529 \times 10^{-11}~\mathrm{m}$$, which was also known at the time.

$$\begin{aligned} k &= \frac{\sqrt{-2mE_n}}{\hbar} \\ &= \frac{\sqrt{\frac{m^2e^4}{16 \pi^2 \varepsilon_0^2 n^2 \hbar^2}}}{\hbar} \\ &= \frac{me^2}{4 \pi \varepsilon_0 n \hbar^2} \\ &= \frac{1}{a_0 n}\end{aligned}$$

And that's enough, more than enough really.

This would not have been possible without the help of my textbook, "An Introduction to Quantum Mechanics" 2nd Edition, by David J. Griffiths (primarily chapter 4). It's a great text book, it helped me heaps in my study (when I actually got around to using, 2 weeks before the exam), was fairly easy to follow, and really interesting.

Thursday, July 9, 2009

Idea Block

I've spent a little bit more time coding for my game recently (as I've had the time), and added a number of new features, but I've come to the point where I can't really think of anything to add. I know there are improvements, new features, etc. I could make, but I just can't think of them.

Some of the things I've done recently are: Different colours when poisoned/frozen/weak; Changed the bullet picture; added new maps; made maps use xml; reworked threading to make it much simpler; basically finished the manual; damage bonuses when using different tower types. But all of these are pretty small changes really.

I'm sure if I could get more people to play it, they'd give my ideas, but as it is now, hardly anyone plays it (I'm around 1 hit a day, if that). But if I leave it where it is now, I can't get too many hits before the site will go down (as I'm on limited bandwidth) - that's an issue I can sort out when it becomes a problem though.

I don't want to let this die though, it's one of my greatest achievements, and I've spent a lot of time writing it. And I think it's good enough for a bunch of people to get enjoyment out of, and it can still be improved. Ah well, I'll mull it over for a bit and see what happens.

Wednesday, July 8, 2009

In mathematics you don't understand things. You just get used to them.

I read this quote the other day, and thought it was awesome. It's by John von Neumann, and according to wikiquote (and therefore true) this was a,

Reply to Felix T. Smith who had said "I'm afraid I don't understand the method of characteristics." —as quoted in The Dancing Wu Li Masters: An Overview of the New Physics (1984) by Gary Zukav footnote in page 208

There are some other great quotes there, like

You should call it entropy, for two reasons. In the first place your uncertainty function has been used in statistical mechanics under that name, so it already has a name. In the second place, and more important, no one really knows what entropy really is, so in a debate you will always have the advantage.

Truth is much too complicated to allow anything but approximations.

and a relatively well known one:

You wake me up early in the morning to tell me that I'm right? Please wait until I'm wrong.

I also want to point out the quote about him, by George Pólya:

There was a seminar for advanced students in Zürich that I was teaching and von Neumann was in the class. I came to a certain theorem, and I said it is not proved and it may be difficult. Von Neumann didn't say anything but after five minutes he raised his hand. When I called on him he went to the blackboard and proceeded to write down the proof. After that I was afraid of von Neumann.

The only place I had hear of him before was because the Neumann function (actually a particular Bessel function) turned up in the solution to the Schrödinger equation for the hydrogen atom.

And just for fun, lets see if anyone can get this sequence:

0.3, 0.4, -0.1, -0.5, -0.8, -2, -4, -10, -60, -300, -2000

Hint: these are all rounded to 1 significant figure as the decimal bit is nasty (probably irrational)