An Expensive Space Heater

Much of the United States is experiencing a bit of a cold spell, my southern California home included (by which I mean it was about 3° Celsius first thing this morning), so I thought now might be a good time to tell this story. On the way to the punchline, we'll visit thermodynamics, computer science, and the ultimate fate of the universe.

Poor climate control in offices is a common complaint. In particular, people often complain about their offices being too cold. I've heard plenty of explanations—it's difficult to keep the temperature consistent across such a large volume of air, different people have different temperatures at which they're comfortable, etc—and I haven't found any of them convincing. Movie theaters and airports, as just a couple of examples, don't seem to have too much trouble keeping large numbers of people comfortable in a large indoor volume. 

I once worked in an office where my desk was under the air conditioning vent. When the air conditioner ran, which was just about always, frigid air directly off the evaporator coils would blow straight onto my desk chair. Even in the hottest part of the summer, I'd have to bring a sweater to work and wear it for most of the day. Once in a while, I'd forget to bring a sweater, and that's when I'd have to get creative.

The Traveling Salesman Problem (TSP) is a well studied problem in computer science. A traveling salesperson needs to visit a specified number of cities, with the order not being important. Not wanting to waste time or gas, the salesperson tries to plan the optimum route that will visit each city with the shortest overall distance traveled. As an example, consider four cities: Los Angeles (as the start and end), San Diego, New York, and Philadelphia. Obviously, the ideal solution would not be Los Angeles - New York - San Diego - Philadelphia - and back to Los Angeles. This would involve crossing the continent four times. Better would be to knock off the two West Coast stops, cross the continent, knock off the two East Coast stops, and cross the continent a second time to return home.

The obvious technique for solving the TSP is what computer scientists refer to as brute force. Compute all possible routes and pick the shortest one. The difficulty with this approach, however, is that the number of possible routes expands very rapidly as cities are added. Solving the TSP for ten cities involves calculating ten times as many routes as is needed for nine cities; eleven cities needs eleven times as many as ten cities; twelve cities need twelve times as many as eleven (or 1320 times as many as nine); and so on. Somewhere around twenty cities, it becomes impractical even for a modern computer to use this technique. Faster processors won't help, either¹. Imagine you built a liquid helium cooled beast of a processor that could handle twenty-four cities in a reasonable amount of time. Great, but if next time you need to do thirty cities, you'd have over a million times more routes to calculate.

A problem that scales in this way is said to scale in factorial time, sometimes expressed as O(n!). Because of the futility of throwing more processing power at O(n!) problems, computer scientists spend a great deal of time trying to come up with algorithms that scale more manageably, like O(n log n) or, better yet, O(n) or, even better, O(1). If you're working on developing an application and you have something that scales in factorial time, it can be a sign that you're doing something wrong.

Now let's take this to an absurd extreme. Consider the TSP for 1000 cities. This is well beyond the twenty cities where the problem becomes intractable. We couldn't expect a computer to calculate all the necessary routes in anything that would be on the scale of minutes or hours or even years. So let's think past that. Could a computer, using the brute force approach, solve the problem in one person's lifetime? No. If a modern computer could have been built at the end of the last Ice Age and worked on the problem throughout the entirety of what we call human history—the Great Pyramids, the Roman Empire, the Aztec and Inca civilizations, the Great Wall of China, the Middle Ages, modernity, the Industrial Revolution, the Apollo moon landings, the Cubs finally winning their third World Series—would it be done now? No. How about we leave it running until the sun expands into a red giant, five billion years from now, incinerating all life on earth? Wouldn't even be close. 

Could a computer ever finish solving the TSP for 1000 cities with brute force? Let's do some back-of-the-napkin math. Let's assume, generously, that a blazingly fast computer could calculate a billion routes in one second. There are 31.5 million seconds in a year, so each year we'd crunch through 3.15 x 10¹⁵ routes. We're going to have to work through roughly 10²⁴⁹ routes. The universe, which fifteen billion years ago was much hotter and denser than it is now, has been expanding and cooling ever since. It is expected to continue expanding and cooling indefinitely. At some point in the future, about 10¹⁰⁰ years from now, all the energy in the universe will be evenly distributed. This is known as the universe's heat death; after that, according to the Second Law of Thermodynamics, nothing happens. No planets, no stars, no trees, no flowers, no nothing. I won't even get a chance to log Vermont for my amateur radio Worked All States award. Needless to say, no computing is getting done after that either. In reality, the universe would have lost its ability to host a structure as complex as a computer long before that, but let's use the heat death as the absolute end of the line for our hypothetical computer. At that point, our computer would have gotten through 3.15 x 10¹¹⁵ routes. If that looks like we're kind of close, it's an illusion of the exponent notation. If we were to write down how close we are to our goal as a fraction, it would be 1 over a 1 with 134 zeros after it. The number of grains of sand on earth is a 1 with 18 zeros after it. If I were to hop in my car, drive to Laguna Beach, pick up some takeout at my favorite Indian restaurant, and put a single grain of sand in my pocket, I would be enjoying lamb vindaloo and basking in the glow of knowing that I was much closer to completing the task of excavating all the sand in the world than our imaginary computer would be to completing its task at the universe's end.

That cold office I worked in was part of a large printing company. Then as now, the Apple Macintosh was the industry standard in the printing and publishing industries. My workstation was a Mac Pro tower. The Mac Pro has (or had; I haven't seen one in a while) a large cooling fan with an exhaust port on the back of the tower. When I forgot my sweater, I would turn the tower around on my desk so that the cooling fan exhaust was pointing at me. The cooling fan's job is to carry excess heat away from the processor. Consequently, the air blowing out the back of the computer is warm, warm enough to overcome the frigid conditions at my desk. When that wasn't enough, I wrote a command line program that attempted to solve the TSP for 1000 cities. The point wasn't to solve the problem—we've seen that that can't be done—but rather to burden the processor with such a computationally intensive task that the processor would heat up and the cooling fan would carry that heat to me. Instrumentation showed that I could raise board temperature by 9° Celsius, and my desk was nice and toasty. I effectively turned a Mac Pro into a very expensive space heater. 

That was a long time ago and there were other ways I could have done the same thing. I could have run a Seti@Home work unit. Today, it would be theoretically possible, if not exactly practical, to mine Bitcoin. Of course, I could have spent less than forty bucks on a space heater, or just remembered my sweater more often. At a time when I was transitioning to a second career as a software developer, I learned a lot from the experience. I also have a funny story that I still get a kick out of telling.  

1. Quantum computers, if they ever become a reality, would be a game-changer. We're not talking about that right now. For the purposes of this post, we're talking only about classical computers, where each bit is represented by a physical object that at any time can be in exactly one of two states, and where the speed of bit flipping is limited by the speed of light.