# 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.

Parents:

• I was slightly con­fused for the next two para­graphs, be­cause I had a silly thought that 10,001 uses only two kinds of digits and would there­fore be cheaper to store.

• Would be nice to be able to see ex­plic­itly why this is so. Not ev­ery­one can do pow­ers of two in their heads.

Also, I just caught my­self re­mem­ber­ing that to com­pute how many wheels I need to store a num­ber, I just need to count the digits! Would be nice to re­mind the reader of this on this page the first time it’s needed.

• For read­ers who just skimmed over $$2^{3,000,000,000,000}$$, and didn’t parse it as “two to the three trillion” (e.g. Eric on his first read­ing), it may be helpful to more ex­plic­itly call out that this “three trillion” is the same num­ber that was in the ex­po­nent ear­lier.

(I tried pre­view­ing a cou­ple of page ed­its, like re­plac­ing $$2^{3,000,000,000,000}$$ with $$2^\text{3 trillion}$$, but wasn’t able to find any­thing that I liked.)

• I think we don’t need that much hand­hold­ing. You’ve got to let peo­ple figure out some of the con­nec­tions them­selves :-p

• I think this para­graph and the pre­ced­ing para­graph would be great op­por­tu­ni­ties for hid­den-text home­work prob­lems.

• This part is es­pe­cially clear.

• Is this a typo? Shouldn’t you buy coins if they are a bet­ter deal? Or am I miss­ing some­thing?