12 1212 12122010-02-03 13:44:32 / rev 2605f1dd03a1+This reasoning tool dissolves difficult problems into manageable pieces.It is a universal solvent for problems social, mathematical, engineering,and scientific.To master a physical tool, we first try it. In that way, we see what it can do,how it works, and eventually study the principles underlying its design.Therefore, the reasoning tool of divide and conquer is introduced usinga mix of examples and theory. The three examples are CDROM design,oil imports, and the UNIX operating system; the two sections of theoryexplain how to increase confidence in estimates and how to representdivide-and-conquer reasoning graphically.2.1 Example 1: CDROM designThe first example is from electrical engineering and information theory.How far apart are the pits on a compact disc (CD) or CDROM?Divide finding the spacing into two subproblems: (1) estimating the CD’sarea and (2) estimating its data capacity. The area is roughly (10 cm)2because each side is roughly 10 cm long. The actual length, accordingto a nearby ruler, is 12 cm; so 10 cm is an underestimate. However, (1)the hole in the center reduces the disc’s effective area; and (2) the discis circular rather than square. So (10 cm)2is a reasonable and simpleestimate of the disc’s pitted area.The data capacity, according to a nearby box of CDROM’s, is 700 megabytes(MB). Each byte is 8 bits, so here is the capacity in bits:700 ·106bytes ×8 bits1 byte∼ 5 ·109bits.Each bit is stored in one pit, so their spacing is a result of arranging theminto a lattice that covers the (10 cm)2area. 1010pits would need 105rowsand 105columns, so the spacing between pits is roughlyd ∼10 cm105∼ 1 µm.13 1313 13132010-02-03 13:44:32 / rev 2605f1dd03a1+That calculation was simplified by rounding up the number of bits from5·109to 1010. The factor of 2 increase means that 1 µm underestimates thespacing by a factor of√2, which is roughly 1.4: The estimated spacing is1.4 µm.Finding the capacity on a box of CDROM’s was a stroke of luck. But fortunefavors the prepared mind. To prepare the mind, here is a divide-and-conquer estimate for the capacity of a CDROM – or of an audio CD, becausedata and audio discs differ only in how we interpret the information. Anaudio CD’s capacity can be estimated from three quantities: the playingtime, the sampling rate, and the sample size (number of bits per sample).Estimate the playing time, sampling rate, and sample size.Here are estimates for the three quantities:1. Playing time. A typical CD holds about 20 popular-music songs eachlasting 3 minutes, so it plays for about 1 hour. Confirming this estimateis the following piece of history. Legend, or urban legend, says thatthe designers of the CD ensured that it could record Beethoven’s NinthSymphony. At most tempos, the symphony lasts 70 minutes.2. Sampling rate. I remember the rate: 44 kHz. This number can be madeplausible using information theory and acoustics.First, acoustics. Our ears can hear frequencies up to 20 kHz (slightlyhigher in youth, slightly lower in old age). To reproduce audiblesounds with high fidelity, the audio CD is designed to store frequenciesup to 20 kHz: Why ensure that Beethoven’s Ninth Symphony can berecorded if, by skimping on the high frequencies, it sounds like wasplayed through a telephone line?Second, information theory. Its fundamental theorem, the Nyquist–Shannon sampling theorem, says that reconstructing a 20 kHz signalrequires sampling at 40 kHz – or higher. High rates simplify the an-tialias filter, an essential part of the CD recording system. However,even an 80 kHz sampling rate exceeded the speed of inexpensive elec-tronics when the CD was designed. As a compromise, the sampling-rate margin was set at 4 kHz, giving a sampling rate of 44 kHz.3. Sample size. Each sample requires 32 bits: two channels (stereo) eachneeding 16 bits per sample. Sixteen bits per sample is a compromisebetween the utopia of exact volume encoding (infinity bits per sample14 1414 14142010-02-03 13:44:32 / rev 2605f1dd03a1+per channel) and the utopia of minimal storage (1 bit per sample perchannel). Why compromise at 16 bits rather than, say, 50 bits? Be-cause those bits would be wasted unless the analog components wereaccurate to 1 part in 250. Whereas using 16 bits requires an accuracyof only 1 part in 216(roughly 105) – attainable with reasonably pricedelectronics.The preceding three estimates – for playing time, sampling rate, and sam-ple size – combine to give the following estimate:capacity ∼ 1 hr ×3600 s1 hr×4.4 × 104samples1 s×32 bits1 sample.This calculation is an example of a conversion. The starting point is the1 hr playing time. It is converted into the number of bits stepwise. Eachstep is a multiplication by unity – in a convenient form. For example,the first form of unity is 3600 s/1 hr; in other words, 3600 s = 1 hr. Thisequivalence is a truth generally acknowledged. Whereas a particular truthis the second factor of unity, 4.4·104samples/1 s, because the equivalencebetween 1 s and 4.4 ·104samples is particular to this example.Problem 2.1 General or particular?In the conversion from playing time to bits, is the third factor a general orparticular form of unity?Problem 2.2 US energy usageIn 2005, the US economy used 100 quads. One quad is one quadrillion (1015)British thermal units (BTU’s); one BTU is the amount of energy required to raisethe temperature of one pound of liquid water by one degree Fahrenheit. Usingthat information, stepwise convert the US energy usage into familiar units suchas kilowatt–hours.What is the corresponding power consumption (in Watts)?To evaluate the capacity product in your head, divide it into two sub-problems – the power of ten and everything else:1. Powers of ten. They are, in most estimates, the big contributor; so, Ialways handle powers of ten first. There are eight of them: The factorof 3600 contributes three powers of ten; the 4.4 ×104contributes four;and the 2 × 16 contributes one.15 1515 15152010-02-03 13:44:32 / rev 2605f1dd03a1+2. Everything else. What remains are the mantissas – the numbers in frontof the power of ten. These moderately sized numbers contribute theproduct 3.6×4.4×3.2. The mental multiplication is eased by collapsingmantissas into two numbers: 1 and ‘few’. This number system isdesigned so that ‘few’ is halfway between 1 and 10; therefore, theonly interesting multiplication fact is that