Fractional digits

When \(b\) and \(x\) are in­te­gers, \(\log_b(x)\) has a few good in­ter­pre­ta­tions. It’s roughly the length of \(x\) when writ­ten in base \(b\). More pre­cisely, it’s the fair price of an \(x\)-digit in terms of \(b\)-digits. But what about when \(x\) or \(b\) is not a whole num­ber? \(\log_{3.16}(5.62) \approx 1.5\); how are we sup­posed to in­ter­pret this fact?

We could ap­peal to the defi­ni­tion of the log­a­r­ithm, ob­serve that \(3.16^{1.5} \approx 5.62,\) and call it a day. But what does that mean? That 3.16 mul­ti­plied by it­self one-and-a-half times is roughly 5.62? That 5.62, writ­ten in base 3.16, is about 1.5 digits long? That a 5.62-digit is worth about 1.5 times as much as a 3.16-digit? What does it mean to mul­ti­ply a num­ber by it­self “half a time”? How would you even write a num­ber down in “base 3.16″? What would a 3.16-digit even look like?

Let’s say that you want to store a lot of data, and digit wheels cost $1. At that price, an ob­ject that can store 3 differ­ent val­ues costs about 48¢, whereas an ob­ject that stores 4 differ­ent val­ues costs about 60¢. What stor­age medium, then, costs ex­actly 50¢? I can think of two:

  1. You and I could buy a digit wheel, split the costs, and share it.

  2. You and I could both pay 50¢ each for a digit wheel, and then toss a coin to see who gets to use it.

How could we split the digit wheel? The digit wheel can be put into any one of ten differ­ent states, la­beled 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. Here’s one way to use it to en­code two differ­ent mes­sages: I choose a num­ber \(a\) be­tween 0 and 1, then you choose a num­ber \(b\) be­tween 0 and 4. Then we put the digit wheel into the state \(5a + b.\) Thus, if you choose 0, the wheel will ei­ther say 0 or 5 (de­pend­ing on which num­ber I choose). If you choose 3, the wheel will ei­ther say 3 or 8 (de­pend­ing on which num­ber I chose). Each num­ber you want to record (0-4) has two rep­re­sen­ta­tions, and I choose whether we use the high one or the low one. Thus, the digit wheel records two mes­sages: 7 means (high, 2) and so on.

Of course, this is not a fair way to split the digit wheel — you get to store a 5-mes­sage whereas I only get to store a 2-mes­sage.noteThus we see that a 10-digit is worth a 5-digit plus a 2-digit, that is, \(\log_{10}(5) + \log_{10}(2) = 1\). Can we do some­thing fairer?

Well, the method­ol­ogy can be used to share ar­bi­trary \(n\)-digits be­tween two peo­ple. If \(x\) and \(y\) are whole num­bers such that \(x \cdot y \le n\) then an \(n\)-digit can be used to store both an \(x\)-mes­sage and a \(y\)-mes­sage at once: You choose the quo­tient of \(n\) di­vided by \(x\), I choose the re­main­der.

Ex­er­cise: How would you use an \(18\)-digit to store both a \(3\)-mes­sage and a \(6\)-mes­sage? How do you store (2, 4) us­ing that en­cod­ing?

Here’s one way: Let \(a\) be the value of the 3-mes­sage (be­tween 0 and 2) and \(b\) be the value of the 6-mes­sage (be­tween 0 and 5). Record \(6a+b.\) Us­ing this en­cod­ing, (2, 4) is stored as the num­ber 16.

You can ver­ify for your­self that there is ex­actly one way to store each (3-mes­sage, 6-mes­sage) pair in an 18-mes­sage un­der this en­cod­ing. <div><div>

(From this we can see that, when \(n = x \cdot y,\) the cost of a \(n\)-digit is ex­actly equal to the cost of an \(x\)-digit plus the cost of a \(y\)-digit. In other words, \(n = x \cdot y\) then \(\log_b(x) + \log_b(y) = \log_b(n),\) no mat­ter what base \(b\) we’re us­ing.)

The fair split of the 10-digit, then, is to let us both store a 3-mes­sage: 3 is the high­est in­te­ger \(x\) such that \(x \cdot x < 10.\) This isn’t max­i­mally effi­cient, though; that en­cod­ing only uses 9 of the 10 pos­si­bil­ities that we paid for, and there­fore it’s not worth our money: Why buy what is effec­tively a 3-mes­sage for 50¢ when the fair price of 3-mes­sages is 48¢? This might be worth know­ing if the mar­ket isn’t sel­l­ing ob­jects that carry 3-mes­sages, and both you and I just need a tiny bit more stor­age, but in gen­eral it’s not worth it.

How­ever, it be­comes more worth­while the more 10-digits we split. You might ex­pect that, when split­ting three digit wheels, we’d each get one digit wheel to our­selves plus a 3-mes­sage each from the third wheel, giv­ing us 30 differ­ent pos­si­ble mes­sages each. How­ever, we can do bet­ter than that if we’re clever. If you pick a num­ber \(a\) be­tween 0 and 30 (for a to­tal of 31 differ­ent pos­si­bil­ities), and I also pick a num­ber \(b\) be­tween 0 and 30, then the num­ber \(31a + b\) can always be stored on 3 digit wheels (be­cause \(31 \cdot 30 + 30 = 960 \le 999\)), so if we’re split­ting three digit wheels, we can ac­tu­ally use them to store two 31-mes­sages. (Why?) This still isn’t max­i­mally effi­cient (the val­ues from 961 to 999 are wasted), but it’s a lit­tle bet­ter. And we can keep in­creas­ing the effi­ciency if we keep go­ing: Five digit wheels can hold two 316-mes­sages; 7 digit wheels can hold two 3162-mes­sages, and so on. (You can ver­ify those num­bers your­self.)

As you can see, when split­ting an \(n\)-digit, the fair split oc­curs at the largest whole num­ber \(x\) such that \(x \cdot x \le n\), in which case we both get to record one \(x\)-mes­sage. This is why it is 316, and not 500, that can most nat­u­rally be seen as “about 2.5 dec­i­mal digits long:” The num­ber that is 2.5 dec­i­mal digits long is the largest num­ber \(x\) such that, given five digits, both you and I can use those 5 digits to store in­de­pen­dent \(x\)-mes­sages. If you store a 500-mes­sage, that only leaves enough space for me to store a 200-mes­sage. If you only store a 300-mes­sage, that leaves enough space for me to store a 333-mes­sage.\(x=316\) is the point where we can both store an \(x\)-mes­sage, be­cause 316 is the largest whole num­ber such that \(x^2 \le 100000.\)

(From this we can de­duce that \(\log_b(316) \approx \frac{5\log_b(10)}{2}\), no mat­ter what the base: A 316-digit is worth about half as much as five 10-digits put to­gether.)

The more 10-digits you split, the more effi­cient it gets — if we split 7 digit wheels, each of us gets to record a 3162-mes­sage; if we split 9 wheels, we each get to record a 31622-mes­sage, and so on. But the split is never max­i­mally effi­cient, be­cause 10 is not a square num­ber: An \(n\)-digit can be split perfectly in half if and only if there is an \(x\) such that \(x \cdot x = n,\) and this can’t hap­pen if \(n\) is an odd power of 10. Thus, split­ting an odd num­ber of digit wheels never makes the fi­nal digit wheel be worth ex­actly 50¢.

You know what stor­age medium is worth ex­actly 50¢? A 50% chance of a 10-digit.

Let’s say we pay 50¢ each for a digit wheel, and then toss a coin to see who gets to use it. How much does this de­crease your stor­age costs? Half the time, you get to re­duce the num­ber you have left to store by a fac­tor of 10; the other half the time, you re­duce the num­ber you have left to store by a fac­tor of 1 (i.e., not at all). How much does that re­duce the num­ber you have left to store, on av­er­age?

On av­er­age, your num­ber gets re­duced by the ge­o­met­ric mean of 1 and 10. Geo­met­ric means “av­er­age out” mul­ti­pli­ca­tions: Let’s say that you have a thing and you’re go­ing to mul­ti­ply it by 2, 12 and 9. At the end of the day, your thing is go­ing to be 216 times larger, and you’re go­ing to have mul­ti­plied it by three num­bers. Geo­met­ric means ask how big each mul­ti­pli­ca­tion was “on av­er­age” — in­stead of mul­ti­ply­ing your thing by three differ­ent num­bers, can we find one num­ber \(y\) such that \(y \cdot y \cdot y = 216,\) such that mul­ti­ply­ing your thing by \(y\) three times is the same as mul­ti­ply­ing by 2, 12, and 9 sep­a­rately? The an­swer is yes, and \(y = \sqrt[3]{2 \cdot 12 \cdot 9} = 6\), as you can ver­ify. Thus, mul­ti­ply­ing your thing by 6 is equiv­a­lent, in ex­pec­ta­tion, to mul­ti­ply­ing your thing by a value se­lected uniformly at ran­dom from the list 12, 9. (For more on this, see Geo­met­ric mean: In­tu­ition.)

Similarly, if we might re­duce the size of the num­ber we want to store by a fac­tor of 1, and we might re­duce it by a fac­tor of 10, then “on av­er­age” we’re re­duc­ing it by a fac­tor of \(\sqrt[2]{1 \cdot 10} \approx 3.16.\) Mul­ti­ply­ing by \(\sqrt[2]{10}\) twice is the same as mul­ti­ply­ing by 1 once and 10 once, so it’s equiv­a­lent in ex­pec­ta­tion to mul­ti­ply­ing by val­ues se­lected uniformly at ran­dom from the list 10.

If three peo­ple are shar­ing a 10-digit, then the amount of digits each one gets to use in ex­pec­ta­tion is \(\sqrt[3]{1 \cdot 1 \cdot 10} \approx 2.15.\) So that’s what a 2.15 digit looks like — a 10-digit shared be­tween three peo­ple. This can be gen­er­al­ized to any prob­a­bil­ity, and any \(n\)-digit for \(1 < n \le 10\) can be in­ter­preted as a digit wheel that you have some prob­a­bil­ity of get­ting to use (How?).

There are a few differ­ent things we can learn from this in­ter­pre­ta­tion. It al­lows us to give a phys­i­cal in­ter­pre­ta­tion to facts like \(\log_{3.16}(5.62) \approx 1.5\), which says that a 5.62-digit is worth one and a half times as much as a 3.16 digit. What’s a 3.16 digit? It’s (ap­prox­i­mately) a 10-digit shared be­tween two peo­ple, i.e., a 10-digit that you have a 50% chance of get­ting to use your­self. What’s a 5.62-digit? It’s a 10-digit that you have a 75% chance of get­ting to use your­self. It’s 1.5x as valuable, be­cause 75% is 1.5x as much as 50%. The up­grade from a 3.16-digit to a 5.62-digit con­sti­tutes 1.5x in­crease in my chance of get­ting to use the digit wheel.

The other thing that this in­ter­pre­ta­tion tells us is that the digit worth ex­actly half an \(n\)-digit is the \(\sqrt{n}\)-digit, both be­cause (1) if you want to use an \(n\)-digit to store two \(x\)-mes­sages for some \(x\), you need \(x \cdot x\) to be at most \(n\); and (2) if you have a 50% chance of get­ting to use an \(n\)-digit and a 50% chance of noth­ing, then that’s equiv­a­lent on av­er­age to a cer­tainty of a \(\sqrt{n}\)-digit.

In case you haven’t no­ticed, we’ve been im­plic­itly us­ing the fact that dou­bling a digit squares the num­ber of pos­si­bil­ities you have available to you: With one 10-digit you can store 10 pos­si­bil­ities, with two you can store \(10^2 = 100.\) Be­cause two \(n\)-digits em­u­late an \(n^2\)-digit, it’s no sur­prise that half an \(n\)-digit is a \(\sqrt{n}\)-digit.

You might be won­der­ing how these square root signs weaseled into a dis­cus­sion about log­a­r­ithms. You also might be start­ing to sus­pect that roots, log­a­r­ithms, and ex­po­nen­tials are se­cretly three sides of the same coin. If so, you’re right, though that’s a topic for an­other day.

Lest you think that this gives us a com­plete in­ter­pre­ta­tion of log­a­r­ithms, note that it still doesn’t ex­plain what’s go­ing on when the in­puts to the log­a­r­ithm func­tion are be­tween 0 and 1. You might think, “well, now that I know what a 3.16-digit is, I can use that in­tu­ition to figure out what a 0.16-digit is” — but it’s not quite as easy as that. A 3.16-digit can be in­ter­preted as prob­a­bil­is­tic ac­cess to a 10-digit, and the same is true for \(x\)-digits when­ever \(x > 1.\) But no mat­ter how many peo­ple share a 10-digit, it’s never worth less than a 1-digit (which is worth­less); \(\sqrt[n]{10} > 1\) no mat­ter how large \(n\) gets. To un­der­stand \(x\)-digits for \(0 < x < 1,\) we need one fi­nal puz­zle piece, cov­ered in the next post.