Numbers

I’ve learned from recent interviews that one thing I am particular bad with are numbers. I was asked to first estimate the number of documents on a person’s desktop. We were sizing up how one would implement a search document feature on a desktop. Before you can say, “Sure, dump it all into a BST,” you want to know just how big that is going to be. You need to know things like how much memory people have, how big is each node in that tree, and how many nodes would fit into a single disk sector. (No, usually that tree can’t just sit in memory).

I think at one point, I used to be pretty good with mental math. That all went away after I started doing proofs and began to thing of actual calculation as part of that other branch of mathematics.

How stupid of me. Jon Bentley talks about making back of the envelope calculations, suggesting that any engineer be well-versed at these types of estimations. He would pose a question like

How much water do you drink in a year?

One of my gripes of Computer Science being in the Engineering department is that I feel detached from the typical engineering process. Blindingly fast processor speeds and memory as cheap as it is has made measurements non-existent for the most part. This is bad and I’m likely doing something wrong.

This has been more or less true until I started taking graphics courses. In graphics, you start hitting that performance wall. For example, you have to think about memory access patterns, stalling the pipeline, and exploiting parallelism. Everything in graphics can be made faster. Even if its fast already, making it faster leaves room for more effects, or lets the AI make a more informed decision.

In my rendering class, my team was plagued with lengthening rendering times. Rendering small versions would take hours and it was here where back of the envelope calculations came into play. It’s not so much the speed of the actual calculation as the skill of sizing up a problem. If it took 4 hours to render a scene at 200 by 200 resolution with 4 samples per pixel on 3 cores, how long would it take to render it at 400 by 400 with 8 samples on 16 cores? During those last few weeks, I’d gotten pretty good about converting seconds to days (1 day is about 90,000 seconds).

I wish I had not taken mental math for granted. It plays such an important role for getting the feel for a problem. Just like how having things like for-loops, BFS, DFS, and recursive patterns at the tips of your fingers, back of the envelope calculations help you get a feel for the time complexity of a problem quickly. I’m reading now about GPU performance and the important of cache coherence. Numbers go whizzing by, and here I am, fumbling with converting between bits and bytes, figuring out the relationship between “million” and the prefix “giga”, and then piecing all those units together like a good high school chemistry student would.

By the way, a neat mental math trick shown to me by my friend. Say you want the product of two numbers, and such that is even (i.e. they are of the same parity). Assume . Let be the average, and .

So, if you can just memorize the squares of numbers, you can solve a lot of products in your head. It’s also not very hard to solve general problems using this technique and doing an extra addition.