Jun 24, 2010

If Cantor Were A Programmer...

When you take math in university, one thing you'll probably come across is the concept of countability. This means that given a set, you can find some way of assigning a natural number to each element of that set - you can count the elements in it.

This guy Cantor discovered in the late 19th century that there are different types of infinities. He did this by analyzing various sets of numbers and discovered that certain infinite sets are in fact "bigger" than other infinite sets. Which is kinda weird, but it works.

I thought it might be fun (my definition of fun is apparently kinda weird) to see what would happen if instead of a mathematician Cantor were a programmer, and what his proof might look like.

Let's take a hypothetical language called C∞, which is kinda like C except that it runs on our magical computer that has an infinite amount of RAM, and thus the integer types in C∞ have infinite precision.

In C∞, we say a type T is countable if we can construct a function like this:
T foo(unsigned int n)
Where foo() satisfies:
1) For every possible unsigned int value n foo() will return a T - this means no exceptions, no crashes, etc.
2) For every possible T value t, there is exactly one unsigned int n1 such that:
foo(n1) == t
We call functions like this one-to-one.

What are some countable types? Well, signed int is countable. Here's a function that will work:
int foo(unsigned int n){
  if (n % 2 == 0){
    return n / 2;
  }else{
    return -(n + 1) / 2;
  }
}
If you start from 0 and continue, this function will produce 0, -1, 1, -2, 2, -3, ...
This turns out to be a one-to-one function, so therefore the signed ints are countable.

It also turns out that signed int pairs are also countable. Suppose we have a type that looks like this:
struct pair {
  int a, b;
};
This type is also countable. The proof is fairly simple when you use a picture, see here for a nice one that is already done. It uses rational numbers, which are a subset of pairs of integers.

What about the real numbers though? This one is a bit trickier. Let's represent a real number like this:
struct real {
  int integerPart;
  bit decimal[∞];
};
What we're doing here for the decimal part is representing it as an infinite series of 1s and 0s. Since we're all computer geeks here, we know that a binary string is just as capable of representing a number as a decimal string, so we still are able to represent any real number using the above type.

Now we show that the reals are not countable using a contradiction. First, we assume that the reals are in fact countable. Let's simplify it a little and only work with the real numbers between 0 and 1, so we'll have a real0 type that is the same as real but with the integerPart field set to 0.
So since real0 is countable (by assumption), it means that we can create a one-to-one function like this:
real0 foo_real(unsigned int n)
Since this function is one-to-one, for every possible real0 value x there is an unsigned int n that will produce x when you call foo_real(n). So let's create an array that has all those real numbers in it:
real0 all_the_reals[∞];
for (unsigned int i = 0; i < ∞; i++){
  all_the_reals[i] = foo_real(i);
}
Now let's cause a problem. Consider the following code:
real0 y;
for (unsigned int i = 0; i < ∞; i++){
  y.decimal[i] = !all_the_reals[i].decimal[i];
}
Why is this a problem? Well, we assumed that all possible values for real0 are in all_the_reals. But for any i, we know that y != all_the_reals[i] because the bit at the ith decimal place is inverted. Therefore we know that y is not in all_the_reals, which means that all_the_reals does not contain all possible real0 values. Therefore there is a real0 value that cannot be produced by foo_real() — a contradiction since we assumed foo_real() is one-to-one. So real0 is not countable, and since real0 is a sub-type of real, real is also not countable.

What does this tell us? Well, we know that with our infinite precision computer there are an infinite number of possible unsigned ints we could have. At the same time we have shown that there is not a one-to-one mapping between the reals and the unsigned ints, so therefore the infinity of the reals is effectively "bigger" than the infinity of the unsigned ints.

Why would a programmer care? Well, this has an implication for computer science. But first, let's ask another question - if there are real0 numbers missing from all_the_reals, how many are there? Is there just one? Or even a finite number? Well, no, and here's why. Suppose there are a finite number of missing real0s. We could then create an array of them:
real0 missing_reals[N];
However we could then still create a one-to-one function:
real0 foo_real_with_missing(unsigned int n){
  if (n < N){
    return missing_reals[n];
  }else{
    return foo_real(n - N);
  }
}
So there must be an infinite number of missing real0s. Are the missing ones here countable? Assume that they are, and create another one-to-one function foo_real2() which gets all these missing real0s. But then we could still create a one-to-one that will grab all the reals returned by foo_real and foo_real2:
real0 foo_real_combined(unsigned int n){
  if (n % 2 == 0){
    return foo_real(n / 2);
  }else{
    return foo_real2((n - 1) / 2);
  }
}
So even the real0s that are missing from foo_real() are uncountable. Crap! In fact based on this we know that even the reals missing from the combination of foo_real() and foo_real2() is uncountable. If we create another one foo_real3() which grabs the real0s outside of foo_real_combined(), it is still uncountable. No matter how many functions we create, they will still not capture all the real0s. What does this have to do with programming? Suppose that our magical computer not only has infinite RAM, but infinite processors. The ith processor will compute foo_real(i) in the first clock cycle, foo_real2(i) in the second, etc. But since the real0s are uncountable, even with infinite processors we wouldn't be able to enumerate them all in finite time. That's something a programmer might care about.

Jun 23, 2010

Bad Economics: The Power of PPP

Take a look at this image (courtesy of this page):



This is what I'd like to call bad economics. I checked a few of the figures and they are correct with respect to exchange rates and minimum wages, however what this image does not reflect is the differences in what economists call "purchasing power". To explain this, the magazine The Economist uses the Big Mac Index which asks, "how much does a Big Mac cost in various countries around the world?" According to their February 2009 data, it would cost you $5.79 USD to buy a Big Mac in Norway (the most expensive), while it only costs you $1.22 to buy a Big Mac in India (the cheapest). Purchasing power measures how much stuff you can buy in a country with a fixed amount of money (say $100 USD).

Let's take a more detailed look at China. For this picture I'm guessing they used China's minimum wage on Wikipedia, which is 960 RMB =~ $140.94 USD per month. This makes about $1691.29 USD per year. In order to get $15 080 USD at that wage, you'd need to work around 8.9 years. So the figure is numerically correct.

My problem with this figure is that it is misleading. Saying that it would take 8.9 years for a Chinese worker to make the same as an American worker would in one year is insinuating that Chinese workers are 8.9 times poorer than American ones. This is not correct. In China, prices are much lower than they are in the United States - this means that Chinese people have a higher purchasing power in China than Americans do in the US. If I were to take $100 USD, convert it to Chinese yuan, and buy a bunch of goods in China, that same bundle of goods would probably cost me around $200 USD if I were to buy them in the United States. That $100 USD is worth twice as much in China as it is in the US.

So the 8.9 years figure is a gross over-estimate of poverty. While it would take 8.9 years to match the American worker's salary, it would only take about 4.5 years to match his purchasing power. The real minimum wage is lower in China, but it's not as much lower as the picture there portrays.

The difference is even bigger for India, $100 USD is worth about 2.8 times as much in India as it is in the US, so the 24.3 years or so that the figure shows is actually about 8.7 years - still a really long time, but the figure certainly overestimates it.

It also goes both ways - purchasing power is lower in France than in the US, so while it may only take you 10 months to earn the equivalent of $15k USD, that money can't buy you as much in France as it would in the US. Same goes for us Canadians, as we often find out when we journey down south!

Jun 19, 2010

CUDA and Fractals

After making some fractal videos of Julia sets, I ran into issues because for certain Julia sets, the image would take a long time to process and I couldn't just do a screen capture to show you a nice animated video (which is what I did for the last video). I decided to sit down and try to figure out how to make it faster. I first tried using shaders, but it didn't work and I got bored (shaders just aren't really something I'm interested in!), so that project failed and the plan to speed up the program faded into the background like most of my projects do.

Recently though I was in Toronto at the Trends in Computing Symposium where a UofT grad student by the name of Duy Minh Dang gave a presentation on using CUDA for computational finance. CUDA is an extension to C released by Nvidia which lets you use the GPU in addition to the CPU for computation. I thought that was a pretty sweet idea, and decided to give it a go to speed up my rendering.

It worked very well, I can render pretty much any Julia set very quickly, so I can make some very interesting videos. Unfortunately running a screen capture program while running the video generator is more than my machine can handle at once, so the fractal video frame rate drops dramatically - if anybody knows a good way for me to pipe the array of raw pixel data to something that encodes to a video file let me know, I've been wanting to figure it out for myself but haven't had the time to figure it out for myself.

So if you want to see the video, you'll need to compile the code yourself. I put up a gist here with the code and compilation command, you need SDL and CUDA in order to compile it. I think you also need an Nvidia card for this, if you have an ATI card you might be able to use Stream to do the same thing. Obviously you'll have to modify the code to whatever Stream uses.

Jun 12, 2010

Colonial

A while back I announced that I was building up a new game using Javascript and gameQuery. My inspiration for this was not actually Farmville, but a board game called Agricola which I played with the Concordia Games Club. Unfortunately I ran in to a few problems:
  • I don't actually like farm video games. Farmville looked boring (and supposedly is). The board game was fun but that's more because you're playing it with real people. This one you just sit around and watch plants grow.
  • gameQuery is based on just straight up jQuery and divs, which ends up getting very slow very quickly. I decided it might be not worth it to keep working on the project.
So I started up another project, I have called it Colonial. This game is based off of the Caesar/Pharoah series of games, which I actually really liked playing. I figure now I'll try to make my own variant so that I can fix some of the little annoying things about those other games.

Also this project uses the HTML5 canvas, which ends up being quite interesting. It is much more performant than gameQuery, and a fair bit more flexible since it is literally a canvas where you just draw things. No need to have all the extra bloat of divs and what-not.

Anyway check it out if you like, all you can do right now is build little houses and give them water, but I'm working on it on a semi-regular basis (I have a job now so I don't work on it as much as I used to) so you'll see updates and bug fixes. At least I say that now ;) as I'm sure you might be aware, I tend to start projects and not finish them fairly often.

Jun 7, 2010

Discovering Fractals: The Discrete Logistic Map

I've discovered another fractal for you, although this one doesn't have a really pretty picture like the other ones do. Instead the beauty of this one is in how weird the behaviour is. It is a very simple equation, yet can still manage to exhibit chaotic behaviour.

Here's the equation in C:
x = a * x * (1.0 - x);
Very simple. The variable x is some variable in between 0 and 1, and a is a fixed constant between 0 and 4.

The interesting part of this is when we execute this equation over and over. For small values of a the result is kinda boring, it converges to some fixed point and stays there. However once you start increasing a, some interesting things pop up. Here is a graph with a = 2.9..4 on the x-axis, and x = 0..1 on the y-axis:
At a = 3, the system no longer has a single fixed point, and begins to oscillate between two points. And around 3.45 it forks again into 4 points, and so on. Eventually you move into regions where it is chaotic, and doesn't really settle down. However even more interesting is how the chaotic regions break up into non-chaotic regions temporarily, and then go back to being chaotic. If you zoom in on these non-chaotic intervals you end up seeing that the region looks the same as the larger picture - which is why this is a fractal, it shows self-similarity.

Why would a programmer care about this? Well it's an example of a simple, completely deterministic discrete system that does not always stabilize, depending on the values of the parameters. It's possible for us to create much more complicated software systems that maybe have the same property - if we run the system 1000 times to see how it behaves, the 1001st (th?) time may still have completely different results. Same for the 1 000 000th and 1 000 001st times. The picture above is with 1000 iterations, but when I up it to 1 000 000 iterations the picture still looks the same (just takes longer to render). Because parts of this system are chaotic, no matter how many times you iterate it will not converge.
In short, an awareness of chaotic systems might be helpful when testing your programs.

If you want to see the code that generated image I have put up a gist that you can look at.

Jun 6, 2010

Statistical vs. Practical Significance

A lot of my statistics posts have talked about this thing called "statistical significance". To repeat for the millionth time (it's that important), when you say something is statistical significant it means that it is not likely that it occurred just by some random fluke.

Statistical significance isn't the only type of significance you should care about. Another type that is important is practical significance. Something is practically significant when you actually care about the results for some practical reason like cost, effort, etc.

Let's look at an example. Suppose we have some code and we want to make some changes. After we make our changes, we want to compare the new version against the old one for something, like performance, memory usage, etc. In this example we'll look at performance. The old version took on average 50ms to run and the new version 10ms. I'll omit the standard errors, just assume that if I say the result is statistically significant then the standard errors are small. Here are our four cases of significance:
PracticalNot Practical
StatisticalIn this one suppose our change is switching data structures in a render loop of a video game. The improvement of 40ms is huge, so it has a high practical significance.Suppose here the difference is a change in the processing time of a PHP script on a website. The result is 40ms faster, but does it really matter?
Not StatisticalSuppose we're back in the video game render loop. If there is no statistical difference between 50 and 10ms, then we have a huge problem - our standard errors are huge. It means some frames will render quickly while others will render slowly. This is a practically significant result.This could be a change to a cron job that runs every night at midnight. You make a small tweak that doesn't really have an effect on performance. There is no need to speed things up, so it doesn't actually matter whether the result is statistically significant or not (assuming that the standard errors are still reasonable, ie. not more than several hours).
Hopefully these examples illustrate the difference between statistical and practical significance. In short, statistical significance is mathematical - it comes from the data and from your confidence (how confident you want to be in your results). Practical significance is more subjective and is based on other factors like cost, requirements, etc. Neither one implies the other, there are situations when one or the other may exist but not both.