Por qué son las representaciones binarias de los grandes números acerca de la $3.3218$ veces tan largo como sus representaciones decimales?

Question

¿Por qué son enormes binario nubers acerca de $3.3218$ veces más que sus decimal contraparte?

Pensé acerca de esto cuando estaba escribiendo este código en Python:

huge_number = 21**31**3 # ** is the power operator
print((len(bin(huge_number)) - 2) / len(str(huge_number)))
# -2 is technical stuff ignore it

No importa lo que el $\texttt{huge_number}$ es (tiene que ser enorme, esto NO funciona para números pequeños), obtendrá $3.3218$. Por qué?

Answer 1

El número de dígitos de la representación de un entero positivo $n$ base $k$ es $$\ell_k(n) = \lfloor \log_k n \rfloor + 1,$$ y la relación de la longitud de una representación binaria de un número a su decimal longitud es $$\frac{\ell_2(n)}{\ell_{10}(n)} = \frac{\lfloor \log_2 n \rfloor + 1}{\lfloor \log_{10} n \rfloor + 1}.$$

Para un gran $n$, los términos constantes en el numerador y el denominador no afectan a la relación de mucho, y tampoco las diferencias entre los valores de $\log_k n$ y sus respectivos pisos (que siempre están en $[0, 1)$) y, así, en un gran $n$ la proporción es de

$$\frac{\ell_2(n)}{\ell_{10}(n)} \approx \frac{\log_2 n}{\log_{10} n} = \log_2 10 = 3.3219\ldots.$$

Comentario De hecho, con un poco más elementales de manipulación de podemos vinculado a la desviación de la relación que usted ha observado: $$\left\vert\frac{\ell_2(n)}{\ell_{10}(n)} - \log_2 10\right\vert < \frac{\log_2 10 + 1}{\lfloor \log_{10} n \rfloor}.$$ Esta obligado probablemente podría mejorarse un poco, pero el uso de esta obligado tenemos que ir a 434 (decimal) números de un dígito (!) para garantizar que la limitación de relación mantiene a dos (decimal) lugares.

Answer 2

El número de dígitos es de aproximadamente(nunca superior a 1) la igualdad para el registro en que la base($\log_{10}(x)\approx$ el número de dígitos de x en base 10). Porque de registro de matemáticas, se obtiene:

$$\frac{\log_{10}(x)}{\log_2(x)}\approx 3.32193$$

Answer 3

Una interesante, si ineficiente para calcular los registros:

import string
import math
import matplotlib.pyplot as plt

huge_number = 21**31**3
b10len = len(str(huge_number))

NUMERALS = string.digits + string.lowercase
def baseN(num, b):
    digits = []
    while num:
        digits.append(NUMERALS[num % b])
        num = num // b
    return ''.join(reversed(digits))

bases = range(2, 30)
lengths = [len(baseN(huge_number, b)) for b in bases]

f, axs = plt.subplots(ncols=2)
axs[0].plot(bases, [b10len/l for l in lengths])
axs[1].plot(bases, [math.log10(x) for x in bases])

plt.show()