Archive

Archive for September, 2009

Brainf*ck

September 29, 2009 1 comment

WARNING: Offensive language ahead! That is, if you’re offended by a completely logical name that makes eloquent usage of the English language.

Read more…

Division by Zero: The Truth

September 21, 2009 4 comments

There are many misconceptions about division by zero. These misconceptions will be reviewed, and there will be discussion as to what division by zero truly means.

Myth: one over zero equals infinity.

It is true that the limit as n approaches zero of one over n is indeed infinity. But a limit and an actual calculation are not the same thing. You cannot divide a number by a number and get a non-number (infinity is not a number).

Myth: Division by zero causes a computer to crash.

Nope. All it will do is cause a program to continue running forever. And that’s just a really unsophisticated program. Here’s some Ruby code for a division algorithm:

  quotient = 0
  val = 1.0
  20.times {
    while x > y
      x -= y
      quotient += val
    end
    y /= 10
    val /= 10
  }

This will effectively divide x by y. But if y = 0, it will continue running indefinitely. It won’t crash. Most real programs, though, won’t let you divide by zero. They either return an error, or return Not A Number.

Why can’t we divide by zero?

Let’s think of this geometrically.

How do you divide three by five? Like this: You have three pizzas and five people. How many pizzas does each person get? Well, three fifths. What if you have zero pizzas and five people? Each person gets zero pizzas: 0 divided by 5 equals 0. But what if you have five pizzas and zero people? How many pizzas does each person get? You could say zero, because no one gets any pizza. Or you could say infinity, since even a tiny fraction of a person would get all the pizza, and zero is like the tiniest fraction of all. But neither of these is really correct.

Here is a mathematical example of why you cannot divide by zero.
x = 1 / 0
Using simple algebra, we can multiply both sides by 0.
x * 0 = 1
We know that anything multiplied by zero equals zero. So we can simplify this.
0 = 1
Oh wait. That doesn’t work, does it. When we try to divide by zero, math breaks.

Or take a look at this:
omg division by zero

Plus, everyone knows that when you divide by zero you get over 9000.

What if you try to make division by zero actually work? Well, first, stop trying. You can’t. But secondly, and more importantly, if division by zero results in an actual number, then you will break calculus. Oops. In order to calculate a derivative, division by zero has to be undefined. So go ahead and try to legitimately divide by zero. But don’t blame me when calculus breaks and then we can’t launch missiles and stuff. And then the commies win.

For example, you want to take the derivative of y = x squared, instead of getting a nice pretty y = 2x, you get a completely crazy graph that makes no sense. Not good.

And that’s why you can’t divide by zero, kids.

Categories: Math

Oooh, shiny!

September 16, 2009 Leave a comment

Firefox has a smart web browser. If I type a word into the URL box, it looks it up on Merriam-Webster.com (my favorite dictionary!) If I type in some other phrase, it looks it up on Wikipedia. And if the Wikipedia page doesn’t exist, it Google searches it. Smart.

Categories: Computer Science

New Keyboard Layout Project: Program Release

September 12, 2009 6 comments

You can find my source code at http://mtgap.bilfo.com/Typing.zip. The new and faster algorithm was written by Chris Johnson, a.k.a. Phynnboi.

The algorithm repeatedly returns this result.

y p u c b  x l d , .
i n e s f  h r t a o
j v ' w z  k m g ; q

Fitness:       2263451098
Distance:      9003112
Inward rolls:  7.04%
Outward rolls: 4.48%
Same hand:     22.80%
Same finger:   0.68%
Row change:    9.01%
Home jump:     0.34%
To center:     4.17%

This is a very good layout. Strangely enough, though, if you run the algorithm for longer it comes up with this layout, even though it has a lower score:

y c o u ;  k m d p w
i s e a .  l h t n r
j z ' , x  v f g b q

Fitness:       2263597180
Distance:      9599916
Inward rolls:  7.20%
Outward rolls: 2.20%
Same hand:     16.85%
Same finger:   0.64%
Row change:    7.64%
Home jump:     0.28%
To center:     1.74%

Which is better and why? How can improvements be made?

Biases of Genetic Algorithms and Simulated Annealing

September 7, 2009 2 comments

Both genetic algorithms and simulated annealing have a serious problem: they get stuck. There are some possible layouts which could be very good, but which the algorithm will never get to since it requires getting past a certain hurdle. So how can this be solved?

1. Let a layout live and mutate for a while before you kill it. The problem with this is one of memory. You’re going to need some really huge arrays to hold all of those layouts.

2. Make one or a few keys inactive. This was inspired by a bug which led to some interesting results. The idea here is that you make a particular letter cost nothing, and run the algorithm as normal. If this letter was acting as a “wall” preventing the algorithm from getting to a good layout, the wall will be taken down. Then, after a few iterations, insert the letter again. I tried this out, and it had minimal effect. On the other hand, it didn’t slow the program down by much, either.\

3. Make one or a few scoring criteria inactive. This could more effectively break down potential walls than #2. This is tricky to implement reliably, though. If you rotate through the scoring criteria, making each one inactive in turn, then the definition of “best” changes every generation and so the program never comes to a stopping point. If you remove each criterion for a few generations but only one time, then you don’t know if it is adequately hurdle-skipping. And then there’s the added problem that the actual fitness will be reduced, and that has to be balanced somehow.

Are there any other methods that could actually work?

New Keyboard Layout Project: Keyboard Version 3.11

September 7, 2009 18 comments

This layout performs significantly better than any other I’ve found. But how good is it really?

Hands: 50% 49%
Fingers: 7% 15% 11% 15% 18% 13% 9% 9%

. l u c b  q h g y ,
o r e s d  p n t i a
' x ; w z  v f k j w

Fitness:       2084759
Distance:      7386.58
Inward rolls:  6.91%
Outward rolls: 6.88%
Same hand:     26.28%
Same finger:   0.58%
Row change:    12.34%
Home jump:     0.14%
To center:     3.50%

Distance and same finger are phenomenally low. Same hand and row changing could be better. But by all measures here, it’s very good. But is it really?

One thing that jumps out at me here is the “ing” trigraph. It is just weird. I practiced with it, though, and it’s actually not too hard. There are some strange words that loop back on themselves like “thingy” or “resurrect”, but I don’t find that to be too hard either, just strange. In fact, MTGAP 2.0 (which I am using right now) has a pretty major loop in the word “themselves”, and that’s not too hard to type.

EDIT: This layout was getting a huge performance boost. Due to a small bug, there were two ‘w’s, only one of which was getting scored. So the layout was essentially 1/30th better than any other layout without the bug. In truth, this is the best layout given the criteria:

y p u c b  x l d , .
i n e s f  h r t a o
j v ' w z  k m g ; q

Simulated Annealing vs. Genetic Algorithm

September 7, 2009 2 comments

When I read about simulated annealing, I considered implementing it instead of a genetic algorithm. But I decided not to. Why? Simulated annealing relies on the assumption that the best layout is next to the second best layout, which is next to the third best layout, etc. But this is likely to be untrue. The second best keyboard probably looks nothing like the best keyboard. But genetic algorithms avoid this problem, through repetition. The “all star” round contains many very good layouts, so it is more likely to converge on the best layout.

But when I saw some results, I had to reconsider. Simulated annealing is seemingly much faster. But how can we get it to converge on the best possible layout? Could we do something like simulated annealing, but then repeat it and pool all the best layouts and evolve those using a genetic algorithm?

I ran some empirical tests, and it turns out that simulated annealing is indeed many times faster than a comparable genetic algorithm. Chris Johnson sent me some source code, and it turns out that it is indeed much faster.

Simulated annealing works sort of like a “smart” genetic algorithm with a pool size of only one. Instead of just making any old mutation, it looks for good mutations to make. This allows much faster convergence. But this strategy, as well as the genetic algorithm strategy, can sometimes skip over very good layouts, or even the best. I will explain in a later post, coming soon.