Sunday, March 6, 2011

An infinite number of mathematicians walk into a bar...

The first one orders a beer. The second orders half a beer. The third, a quarter of a beer. Before the fourth mathematician can place his order, the bartender says "You're all idiots", and pours two beers. 
Yes, dumb math joke. But how easy is this to prove? We could form a mathematical proof that shows this must be true (I think I did this in class at one point), but where's the fun in that? Monte Carlo methods don't really prove much, but I think they're a fun way to solve1 this kind of math riddle.

So, how fast can we write a Clojure function that figures this out for us? Pretty fast- it's a one liner2.
(reduce + (pmap #(/ 1 (Math/pow 2 %)) (take 200000 (iterate inc 0))))
I'm going to use this post to telly you how this works. It's best to try to read Clojure code from the inside out. Let's start with
(take 20000 (iterate inc 0))
This will generate a lazy sequence of the numbers 0 - 19999. The (iterate inc 0) part is actually an infinite (but luckily, lazy) sequence. Pretty cool, huh?

The next block is the map function
(pmap #(/ 1 (Math/pow 2 %)) (take 200000 (iterate inc 0)))
The map documentation shows that it takes a function and a sequence of numbers. We've already generated our vector, so what about this function? 

The #( syntax means we will be using an anonymous function. The % becomes the variable we pass in to the function; in this case we're passing in each number from 1-19999. This uses Java's pow function from java.lang.Math to raise 2 to that power, then divide into 1. Notice how easy it is to use Java libraries within Clojure code.

So now we have our two arguments to pmap. As the documentation says, this function is exactly equivalent to map, but has the added benefit of the map tasks in parallel. Since our functions are pure and don't depend on each other for computation, we can parallelize them. So, we use pmap instead of map, and boom3! Instant parallelization. I love this game.

Now we have a 20000 element long sequence kinda like this
[1 1/2 1/4 1/8 1/16 1/32 ...]
Each of these corresponds to a drink that one of our infinite mathematicians ordered back in our joke4. The last thing we need to do is sum all of these fractions up.
(reduce + (pmap #(/ 1 (Math/pow 2 %)) (take 200000 (iterate inc 0))))
And that brings us back to our original one liner. Now that we understand the inside, we can see that reduce takes a function (yes, + is just a function) and a sequence. It returns whatever it gets by "folding" the answer from each call of the function to the next one (check the docs or Wikipedia for a real explanation), leading us to get a single number from our sequence. 

The answer is 2 by the way. Probably could have saved you a bunch of time if I just said that in the beginning.

How could this be made cooler? By using 20000 elements, we're ensuring that we reach a point where the rounding inaccuracies of floating point numbers show us an answer of 2. Of course, the actual answer never reaches two. However, we could write our own recursive function (which would replace the reduce call) that stopped execution when it noticed that the input sum hadn't changed after calculation, meaning we'd reached our maximum precision.

1 Using "solve" in the loosest sense of the word.
2 Blogs have magical properties that turn amazing one liners into ugly multi-line messes. At one point it was one line, and in a 80 character window too.
3 This is the one and only time this blog will link to Steve Jobs. Get your fill while it lasts.
4 Were you aware that analyzing a bad joke to death doesn't make me like it any more?

No comments:

Post a Comment