# Sideband #40: Chessboard of Rice

I recently mentioned a parable about grains of rice and a chessboard. If you were industrious enough to try your own interweb search for [parable 64 squares grains] you might be ahead of me. Or you may have known the parable already. For the rest of you, here’s the deal.

Stripped of the narrative, it’s about taking a chessboard and placing a single grain of rice in the first square (in some versions, it’s a grain of wheat). In the second square, place two grains of rice—double the amount in the first square. In the third square use double the grains of the second square. For each square on the chessboard, use twice as many grains of rice as used for the previous square.

I’ll come back to the punchline, but I stripped the narrative. Let me fix that.

I was going to tailor my own from the whole cloth, but I decided to look around to refresh my mind about the pattern and instead found an off-the-rack number that looks just great. It’s recently minted, and it’s called The Power of Compounding. I couldn’t put it better myself, so I didn’t.

[Update 12/4/2013] I’ve noticed the link above is broken. Rather than link to another version, I thought I’d just weave a short version here. Bonus: In poking around, I may have found the original parable! It involves the man who invented chess. The country’s ruler was so impressed he insisted the man accept a bountiful gift, despite the man’s protests he wanted nothing. Finally the inventor relented and asked the king to fill the squares of his chessboard with grains of wheat. One in the first square, two in the next, then four, eight and so on, doubling in each square.]

If you would like to dig deeper on your own, you can start at the Wikipedia article that discusses it: Wheat and chessboard problem.

Here’s the punchline: if you could pour grains of rice for all 64 squares on the chessboard, you end up pouring a total of 18,446,744,073,709,551,615 grains of rice.

If that number sounds familiar, you may have been reading this blog. That number is 18 exabytes (18 giga-giga-bytes), which I first mentioned writing about loading a lot of movies on a very large disc drive. Specifically, that is the number of unique addresses you get with 64 bits: 18 exabytes.

Actually that is one less than the number I mentioned. That number ended with 616; the number above ends with 615. The difference is that here we’re not counting the empty chessboard with no grains of rice. In previous talk about 64 bits, all 64 bits being off (all chessboard squares empty) is the number zero, which I’ve also mentioned before. The parable skips the empty chessboard and starts with one square, one grain of rice.

We can think of the chessboard as a binary number. Each chessboard square is one bit. The amount of rice that is poured for a square (twice the amount used for the previous square) is the value of that bit. Each added bit is worth twice as much rice as the bit before it.

As the parable mentions, at first the doubling doesn’t seem to amount to much: 1, 2, 4, 8, 16, 32, 64, 128… At eight squares, even after doubling seven times, we’ve just broken 100. We can pause here to note that the total amount of rice poured is 1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 = 255. That is the sum of the bit values.

Let me draw the connection to binary numbers more clearly. If a square has rice poured on it, that bit is “on” (is set to “1”). If there is no rice for a square, that bit is “off” (is set to “0”). In the parable the squares are set progressively. No square is ever reset to off once filled. From a binary number point of view, it progresses like this: 1, 11, 111, 1111, 11111, 111111, 1111111, 11111111. The last one represents eight squares filled with grain, each one holding twice as much as the one before.

If we imagined sweeping away the rice from the middle four squares and leaving the rice in the two end squares on each side, we’d have 1 + 2 + 64 + 128 = 195 grains of rice. The binary number represented by the squares now is 11000011. (I haven’t said anything about which way is which on the bit strings. For now it doesn’t matter.)

As the parable also mentions, after a while the doubling becomes serious. 16 thousand, 32 thousand, 64 thousand, 128 thousand, 256 thousand. Wait, that’s a quarter million, and we’re only 18 squares in! By 25 squares we hit 33 million; at 30 squares we cross the billion mark. At 40 squares we reach trillion (million million), and at 50 squares we’re over 1000 times beyond that. By 60 squares, we’ve got over 1 billion billion grains of rice, and we reach the final count four squares later: 18,446,744,073,709,551,615 grains of rice.

The interweb returns varying numbers for “how many grains of rice in a pound.” The number goes as low as 16,000 to as high as 29,000. One source measured it at 22,680.  Short grain rice would have a higher number of grains per pound; maybe as much as three or four times.

Let’s assume 30,000 grains of rice in a pound and see what we have on the chessboard.

Well, that’s 307,445,734,561 tons of rice. The Empire State Building weighs in around 370,000 tons, so there’s almost 1,000,000 times as much rice.

One million Empire State Buildings worth of rice.