mathemagicio.us

Tradition can often be a retarding force in mathematics. Advancements in logic were held back by centuries due to a collective belief that Aristotle had it all figured out and there was nothing left to discover. Non-Euclidean geometry wasn’t seriously studied until the 1800s because no one could think of the parallel postulate being false.

We nowadays tend to recognize the dangers of blindly following tradition, yet in virtually all areas of mathematics we continue to adhere to notational lunacy, and pass it on to future generations starting as early as in junior high school.

This lunacy is so deeply ingrained in our minds that we see nothing wrong with the following expression:

Let’s decipher the above. We start with a number x, apply f, square the result, and finally apply sin. Yet how do we recover this order of operations from the symbols above? Starting at x in the middle we move left to f, right to the , and far left to the sin.

Although we read and write left-to-right, and so naturally imagine time evolving in this direction, the notation f(x) (due to Euler) means the opposite: start with x, then apply f. Even worse is when we have an expression like f(g(h(x))). The very first operation is written on the very right, and the final operation is written on the very left, in complete contrast to how we normally think.

Worse still is that we do read some operations left-to-right, like raising to a power, and so we end up mentally zig-zagging across mathematical writing to even decipher mathematical expressions.

But worst of all is the following: when we write a function , A denotes the input domain, and B denotes the output domain: input on the left, output on the right. As we’d expect in a sane world. If we also have a function , this left-to-right notation suggests we should be able to follow the arrows (A to B to C) to compose f and g. Yet, of course, the composite is called gf rather than fg. When reading gf we are meant to mentally reverse the direction of the arrows, so that and , although we never write this way!

This is psychotic behaviour, and we should put a stop to it. I suggest we forget tradition, and instead succumb to notational common sense to write expressions like x.f.g rather than g(f(x)).

This may seem bizarre at first, but at least one group of scientists adopted this notation years ago. In object-oriented programming languages a mental shift is required, where one stops thinking that functions have certain inputs, and instead starts to see that inputs have certain functions. In doing so, the left-to-right notation becomes completely natural, and we would write deck.sort.pop to sort a deck of cards and remove the last one, rather than pop(sort(deck)) as we’d expect in the mathematicians’ ridiculous notation.

I believe that a notational shift would make all of our lives easier in the long run, but of course it will likely never happen. Just as negative charge will always correspond to an excess of electrons, Euler’s notation is an unfortunate convention that is simply known by too many people. As a result, already-difficult subjects like category theory are made even more maddening for silly reasons, and high school students have far more difficulty learning precalculus than they should.

Help us, Barack Obama, we need Change.

Uncategorized CS, Math

A new post at Computational Complexity asks the following question:

(Problem 1.) You are trying to determine a secret integer x between 1 and n inclusive, using only queries of the form “is x = a (mod b)?” for integers a and b of your choosing. How many queries are required to determine x in the worst case?

And more restrictively,

(Problem 2.) Same as above but you are only allowed to make queries where b is prime.

The comments section seems to reveal at least a partial solution, but these are fun problems, so at least give them a shot before reading the solution there (or here.) If you’d like the solution spoiled anyway, read on! Read more…

Uncategorized Complexity, CS, Math

Who says computer scientists don’t know how to have fun? As a counterexample, consider a new post over at Gödel’s Lost Letter that was obviously the result of some Wednesday-night festivities and intoxication.

I think, in a sense, we are the accelerators. As we smash ideas together sometimes we discover the further structure of our fundamental particles—our complexity classes.

Duuuuude.

Uncategorized Complexity, CS, Science!

Here’s a real excerpt (slightly modified to protect the stupid, and now fixed) from a web app I inherited. GRAAAAAAAARGH!

def encrypt_password
  ...
  self.salt = md5("#{Time.now.to_s}-#{login}")
  ...
end
 
def generate_confirm_hash
  ...
  self.confirm_hash = md5("#{Time.now.to_s}-#{email}")
  ..
end

Pro-tip for hiring managers: ask candidates to identify problems in the above code, and smack any who fail to do so.

Uncategorized CS, Programming, Ruby, Security

All right, class. Who can tell me what the following program will output? Bear with me, I promise this gets interesting.

1
2
3
4
5
6

int main ()
{
  int x = 0, y = 0;
  y = ++x + 10;
  printf("%d, %d\n", x, y);
}

That’s easy, it’s exactly what you expect: “1, 11″.

What about if you replace line 4 with the following?

y = x++ + 10;

Again, easy! This time, the expression x++ evaluates to the value of x before it is incremented, so the answer is “1, 10″.

Now, what about this?

1
2
3
4
5
6

int main ()
{
  int x = 0;
  x = ++x + 10;
  printf("%d\n", x);
}

This is no different than the first example, except that we’ve chucked the variable y, so the answer is “11″.

Last question: (and I’m sure you can see where this is going) what if you replace line 4 with the following?

x = x++ + 10;

I’m obviously trying to trick you, so you must realize that the answer is surprisingly also “11″, but can anyone tell me why it is so?

Extra credit: explain what happens if you replace line 4 with this seemingly-equivalent statement:

*(&x) = (x++) + 10;

Uncategorized CS, Programming

Virtually everyone with a CS blog (see Scott Aaronson, Luca Trevisan, and the Complexity Blog) has for the past several weeks been going on about Mark Braverman’s recent proof of the Linial-Nisan conjecture. I don’t have too much to add to the discussion, being a neophyte to much of this stuff, but I did attend a talk Braverman gave at the University of Calgary today, in which he outlined his proof (which is remarkably short, for a proof of a conjecture that took nearly 20 years to solve.) Braverman illustrated his arguments with pictures, which really helped me get a handle on his techniques. Read more…

Uncategorized Complexity, CS

Despite rumors to the contrary, Barack Obama is not a secret bubble sorter.

Uncategorized CS, Google, Obama, Youtube

Ruby is a wonderful language, largely deserving of the fanaticism surrounding it. There are a number of ways you can exploit its syntax to write concise, beautiful code. For example, to shuffle an array…

deck.sort_by{ rand }

…or to pick out certain elements of one…

deck.find_all{ |card| card.suit == Clubs }

…or to seamlessly cache computations.

def average_earnings
  @average_earnings ||= some_lengthy_computation
end

(Above, the ||= operator acts analogously to the familiar += operator. So if the instance variable @average_earnings already has a non-nil value, it is returned without any further computation. If on the other hand it is nil, then some_lengthy_computation is performed, @average_earnings is set to it, and returned.)

In addition, there are also a number of ridiculously short applications written in it, including a web server in 70 lines of code, a message board application in 500 lines, and its slightly more verbose successor.

In addition to these, I present a proof of concept of my own: Mathematica and Maple-like symbolic differentiation in about a hundred lines of code.

Read more…

Uncategorized CS, Math, Programming, Ruby