Emulating digits

https://arbital.com/p/emulating_digits

by Nate Soares Jun 24 2016 updated Jun 25 2016


In general, given enough $~$n$~$-digits, you can emulate an $~$m$~$-digit, for any $~$m, n \in$~$ [45h $~$\mathbb N$~$]. If $~$m < n,$~$ you can emulate an $~$m$~$-digit using just one $~$n$~$-digit — in other words, you can use a Digit wheel like a $~$7$~$-digit if you want to, by just ignoring three of the possible ways to set the digit wheel. If $~$m > n,$~$ things are a bit more difficult, but only slightly.

Basically, with 2 $~$n$~$-digits, you can emulate a $~$n^2$~$-digit, as follows. Using your two $~$n$~$-digits, encode a number $~$(x, y)$~$ where $~$0 \le x < n$~$ and $~$0 \le y < n$~$. Interpret $~$(x, y)$~$ as $~$xn + y.$~$ You have now encoded a number between 0 (if $~$x = y = 0$~$) and $~$n^2 - 1$~$ (if $~$x = y = n-1$~$). Congratulations, you just used two $~$n$~$-digits to make an $~$n^2$~$ digit!

You can use the same strategy to emulate $~$n^3$~$-digits (interpret $~$(x, y, z)$~$ as $~$xn^2 + yn + z$~$), $~$n^4$~$-digits (you get the picture), and so on. Now, to emulate an $~$m$~$-digit, just pick an exponent $~$a$~$ such that $~$n^a > m,$~$ collect $~$a$~$ copies of an $~$n$~$-digit, and you're done.

This isn't necessarily the most efficient way to use $~$n$~$-digits to encode $~$m$~$-digits. For example, if $~$m$~$ is 1,000,001 and $~$n$~$ is 10, then you need seven 10-digits. Seven 10-digits are enough to emulate a 10-million-digit, whereas $~$m$~$ is a mere million-and-one-digit — paying for a 10-million-digit when all you needed was an $~$m$~$-digit seems a bit excessive. For some different methods you can use to recover your losses when encoding one type of digit using another type of digit, see Fractional digits and Fractional bits. (These techniques are fairly useful in practice, given that modern computers encode everything using bits, i.e. 2-digits, and so it's useful to know how to efficiently encode $~$m$~$-messages using bits when $~$m$~$ is pretty far from the nearest power of 2.)