Exchange rates between digits

Let’s say that you want to store a lot of data, us­ing phys­i­cal ob­jects such as coins, dice, or digit wheels. For con­crete­ness, let’s say that you’re go­ing to be given an ar­bi­trary num­ber be­tween one and \(2^\text{3,000,000,000,000}\) (a.k.a. a ter­abyte of data), and you need to make sure you have enough phys­i­cal ob­jects to write that num­ber down.

Let’s say that a coin costs 1¢. Be­cause \(n\) coins can be used to en­code any one of \(2^n\) differ­ent pos­si­bil­ities, you could get the job done with three trillion coins, which would let you en­code the num­ber (in bi­nary) for the low low cost of thirty billion dol­lars. (At the time of writ­ing this, three trillion bits of data will ac­tu­ally run you about $60, but leave that aside for now. Pre­tend you can’t use mod­ern tran­sis­tors, and you have to use com­par­a­tively large ob­jects such as coins to store data.)

In­stead of buy­ing coins, you could also buy digit wheels, and use those in­stead. Be­cause digit wheels can store more val­ues than coins, it takes fewer digit wheels than coins to do the job. If digit wheels also cost 1¢, you should just buy digit wheels; that will cost a mere $9B. If in­stead digit wheels cost a mil­lion dol­lars apiece, you should prob­a­bly buy coins in­stead. Some­where in be­tween those two prices, digit wheels switch from be­ing a good deal to be­ing a bad deal. The ques­tion is, if coins are worth 1¢, then how much is a digit wheel worth? At what price should you buy wheels in­stead of coins, and at what price should you buy coins in­stead of wheels?

At a first glance, it may seem like the fair price is 5¢ per wheel. A coin can store two val­ues (by be­ing placed ‘heads’ or ‘tails’), while a digit wheel can store ten. Ten is five times larger than 2, so per­haps the price of a digit wheel should be five times the price of a coin. How­ever, if digit wheels cost 5¢, you should ig­nore digit wheels en­tirely and buy coins. Why? Be­cause for only 4¢, you could buy four coins, which can hold \(2^4=16\) differ­ent val­ues. Four coins store a 16-digit, and a 16-digit is worth more than a 10-digit, so you would have no rea­son to even con­sider buy­ing digit wheels at a price of 5¢ per wheel.

So what is the fair price for a digit wheel? 4¢ is still too high, be­cause that makes a 10-digit cost the same as a 16-digit, and the 16-digit is always bet­ter at that price. What about 3¢? At that price, the an­swer is much less clear. On the one hand, spend­ing 3¢ on coins gets you the abil­ity to write down only 8 pos­si­bil­ities, while spend­ing 3¢ on wheels lets you write down 10 differ­ent pos­si­bil­ities. On the other hand, if you’re try­ing to store the num­ber 101, you need ei­ther 7 coins (7¢, be­cause \(2^6 < 101 < 2^7\)) or 3 wheels (one per digit, be­cause a wheel stores a digit, for a to­tal of 9¢), in which case the coins are bet­ter.

Given that digit wheels can store ten val­ues and cost 3¢ each, and coins can store two val­ues and cost 1¢ each:

Ques­tion: When stor­ing the num­ber 8000, should you buy coins or wheels?

Wheels. To store 8000, you need 13 coins (be­cause \(2^{12} < 8000 < 2^{13}\)) for a cost of 13¢, but only 4 wheels (be­cause 8000 is 4 digits long) for a cost of 12¢.

Ques­tion: When stor­ing the num­ber 15,000, should you buy coins or wheels?

Coins. Stor­ing 15,000 costs 14 coins ($2^{13} < 15,000 < 2^{14}$) or 5 wheels; given that wheels cost 3¢ and coins cost 1¢, the 14 coins are cheaper.

Ques­tion: When stor­ing the num­ber 230,000, should you buy coins or wheels?

It doesn’t mat­ter. Stor­ing 230,000 takes ei­ther 18 coins or 6 wheels, which costs 18¢ ei­ther way.

At 3¢ per digit wheel, whether you should buy coins or wheels de­pends on which num­ber you want to store.

But once the num­ber you’re stor­ing gets large enough, the digit wheels be­come a bet­ter deal, and stay that way. In this case, the fi­nal tran­si­tion hap­pens when the num­ber you’re stor­ing is 11 digits long or longer. Why? Say that the num­ber \(x\) you want to store is \(n\) digits long in dec­i­mal no­ta­tion.\(n\) digit wheels can always en­code more pos­si­bil­ities than \(3n\) coins (be­cause \(10^n > 2^{3n}\) for all \(n\)), but some­times \(x\) can be writ­ten us­ing fewer than \(3n\) coins (as in the case of 15,000). This stops hap­pen­ing once \(n\) is so large than \(10^n\) is \(2^3\) times larger than \(2^{3n}\), at which point no \(n\)-digit num­ber can be en­coded us­ing \(2^{3(n-1)}\) or fewer coins. This hap­pens once \(n \ge 11,\) i.e., once \(x\) is at least 11 digits long. (Proof.)

This prob­a­bly isn’t too sur­pris­ing: For 3¢ you can ei­ther buy 3 coins or one digit wheel. The coins store 8 pos­si­bil­ities, the wheel stores 10, and it’s no sur­prise that a huge col­lec­tion of 10-digits is un­am­bigu­ously bet­ter than an equally sized col­lec­tion of 8-digits.

So digit wheels are worth more than 3x as much as a coin, and less than 4x. How can we find the right price ex­actly? We could use ex­actly the same ar­gu­ment as above to check whether 3.5¢ is too high or too low, ex­cept that it’s not clear what it would mean to buy “three and a half coins.” We can get around that prob­lem by con­sid­er­ing ten-packs of coins vs ten-packs of digit wheels. If wheels cost 3.5¢ and coins cost 1¢, then with 35¢, you could ei­ther buy 10 wheels or 35 coins. Which en­codes more pos­si­bil­ities? The coins, be­cause \(10^{10} < 2^{35}.\) Thus, by a gen­er­al­ized ver­sion of the ar­gu­ment above, for num­bers suffi­ciently large, the coins are a bet­ter deal than the wheels — at that price, you should buy wheels.

As you can ver­ify, \(2^{33} < 10^{10} < 2^{34},\) so the fair price must be be­tween 3.3¢ and 3.4¢. And \(2^{332} < 10^{100} < 2^{333},\) so it must be be­tween 3.32¢ and 3.33¢. We could keep go­ing, and keep get­ting digits of the fair price. And we could keep go­ing for­ever, be­cause the fair price is ir­ra­tional. (Why?)

In gen­eral, if digit wheels cost \(p\) times as much as coins, the gen­eral ar­gu­ment we’ve been us­ing says that if you’re stor­ing a large num­ber and \(2^p > 10\) then you should buy coins, whereas if \(2^p < 10\) then you should buy digit wheels. Thus, the fair price must be the num­ber \(p\) such that \(2^p = 10,\) and its first three digits are 3.32.

In other words, while a digit wheel holds 5 times as many val­ues as a coin, it is only worth about 3.32 times as much as a coin (in terms of its abil­ity to store data). Why? Be­cause it takes about 3.32 coins to em­u­late a digit-wheel. What does that mean? Well, 3 coins is not enough to em­u­late a digit wheel (3 give you only 8 pos­si­bil­ities), 4 coins is more than enough (4 give you 16 pos­si­bil­ities). And 33 coins is not enough to em­u­late 10 digit wheels, but 34 coins are more than enough. And 332 coins are not enough to em­u­late 100 digit wheels, but 333 coins are more than enough.

A digit wheel isn’t worth 5 times as much as a coin be­cause, when you buy mul­ti­ple coins, their data stor­age ca­pac­ity mul­ti­plies, rather than adding. Each new coin lets you say twice as many things, not just two more things. With five coins you can store \(2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 = 32\) differ­ent val­ues, not \(2 + 2 + 2 + 2 + 2 = 10.\) When find­ing the ex­change rate be­tween coins and digit wheels, the ques­tion is not “How many more val­ues does a digit wheel have writ­ten on it?” Rather, the ques­tion is “How many coins does it take to em­u­late a digit wheel?” The an­swer to that ques­tion is “More than 332 coins per hun­dred digit wheels, less than 333 per hun­dred.”

The fair price \(p\) of digit wheels (in terms of coins) is the num­ber \(p\) such that \(2^p = 10\) ex­actly. We have a name for this num­ber, and it’s \(\log_2(10),\) and the ar­gu­ment de­scribed above is a sim­ple al­gorithm for com­put­ing log­a­r­ithms. (Log­a­r­ithm out­puts are “difficult to calcu­late but use­ful to have,” in gen­eral.)

Thus, we can look at \(\log_b(x)\) as de­scribing the fair price of \(x\)-digits in terms of \(b\)-digits. For ex­am­ple, if coins are worth 1¢, then dice are worth \(\log_2(6) \approx 2.58\) cents, as you can ver­ify by check­ing that \(2^2 < 6 < 2^3\) and \(2^{25} < 6^{10} < 2^{26}\) and \(2^{258} < 6^{100} < 2^{259}.\) (Ex­er­cise: Find the next digit of \(\log_2(6)\) us­ing this method.)

This in­ter­pre­ta­tion is a great in­tu­ition pump for what \(\log_b(x)\) “re­ally means” if \(b\) and \(x\) are whole-num­bers. Imag­ine two sets of ob­jects, one (say, weird dice) that can be placed in \(b\) differ­ent states, and an­other (say, weird wheels) that can be placed in \(x\) differ­ent states. Imag­ine you’re stor­ing a re­ally re­ally large num­ber, and imag­ine that the \(b\)-ob­jects cost 1¢. At what price of \(x\)-ob­jects would you be in­differ­ent be­tween us­ing \(x\)-ob­jects ver­sus \(b\)-ob­jects to store data? In other words, how many \(b\)-ob­jects does it take to “em­u­late” an \(x\)-ob­ject?

Prob­ing this in­ter­pre­ta­tion also ex­plains many of the prop­er­ties of the log­a­r­ithm. For ex­am­ple, the fact that \(\log_b(x)\) is the fair price of \(x\)-digits in terms of \(b\)-digits im­me­di­ately im­plies that \(\log_x(b) = \frac{1}{\log_b(x)}\), be­cause if an \(x\)-digit is worth three \(b\)-digits then a \(b\)-digit must be worth a third of an \(x\)-digit.

This in­ter­pre­ta­tion still doesn’t shed light onto what log­a­r­ithms are do­ing when their in­puts are not whole num­bers. For ex­am­ple, what’s \(\log_{1.5}(2.5)\)? What the heck would an ob­ject that can be placed into “1.5 differ­ent states” even be? As we will see shortly, this no­tion of there be­ing a “nat­u­ral ex­change rate” be­tween digits re­veals an in­ter­pre­ta­tion of the log­a­r­ithm that ex­plains what it’s do­ing with frac­tional in­puts.