Cómo calcular el número de dígitos decimales de un número binario?

Question

Iba a preguntar esto en Stack Overflow, pero finalmente decidió que esto era más matemáticas de la programación. Todavía puede llegar a estar equivocado acerca de eso, pero...

Dado un número representado en binario, es bastante fácil derivar una representación decimal usando división de enteros y restos de extracto de dígitos en orden inverso. A continuación, basta con contar el número de dígitos que se extrae.

Sin embargo, me preguntaba sobre el cálculo exacto del número de dígitos decimales de manera más eficiente, evitando el cálculo de los dígitos real.

A primera vista, esto es fácil. En primer lugar, contar los dígitos binarios necesarios (es decir, determinar la posición de la mayor conjunto de bits). Muchos procesadores de someterse a una operación para hacer esto directamente, y hay poco-jugueteando algoritmos para hacer en O(log n) tiempo donde n varía con el ancho de una máquina registradora. En una posición arbitraria entero, normalmente se sabe cuántos máquina de palabras, por lo que generalmente, usted puede saltar directamente a la palabra más significativa.

Una vez que usted sabe el tamaño de dígitos binarios, puede escalar por $\log 2 \over \log 10$ para obtener el número de dígitos decimales. Tipo de.

El problema es que este factor de escala es (creo) un número irracional. Si usted tiene un número máximo de dígitos que usted necesita preocuparse acerca de, usted puede utilizar una aproximación racional y sólo tendrá que preocuparse de conseguir el redondeo a la derecha.

La pregunta es, por lo tanto - hay una forma de determinar este número de dígitos decimales de manera eficiente y precisa de los números de cualquier tamaño? Hay (por ejemplo) un enfoque completamente diferente para el cálculo de la que no he pensado?

Answer 1

Yo iba a publicar esto como un comentario, si yo puedo, porque se parece demasiado simple para una respuesta. Ya se ha dicho que usted puede encontrar el más alto de bits con una sola instrucción (si el número se ajusta a un registro). Para cada resultado $r$ (es decir, su número está entre el$2^r$$2^{r+1}-1$), sólo hay dos posibles números de $k$ $k+1$ de los dígitos decimales. Por lo que sólo podría utilizar $r$ como un índice en una tabla de búsqueda que almacena $k$$10^k$, y la salida de $k$ si su número es menor que $10^k$ o $k+1$ lo contrario.

Answer 2

Con no hay mejor respuesta, voy a añadir un poco de lo que he dicho en la pregunta para obtener esta cerrado.

Hay una serie de cálculos para los logaritmos (http://en.wikipedia.org/wiki/Logarithm), por lo que, en principio, podría calcular la base 10 del registro directamente. Este sería torpe y lento, a pesar de que, como para enteros de precisión arbitraria una máquina de flotación/doble no es lo suficientemente precisa. Yo probablemente necesidad racional de la biblioteca, y los racionales involucrados no sería sencillo.

Puede ser posible el uso de una imprecisa base de conversión el factor. Con una subestimación del factor, se obtendría una estimación de registro de valor. Dividir por 10^x para que el registro de valor, a continuación, repita tan a menudo como sea necesario para su estimación.

El problema es que la división por 10^x no es trivial, a menos que usted esté trabajando en base 10.

Probablemente la mejor manera de seguir con la repetición de la división por 10 o potencias de 10, por lo menos. La construcción de una lista de poderes (10^1, 10^2, 10^4, 10^8 y así sucesivamente) por el cuadrado de no ser demasiado duro. Detener cuando se supera el número de destino, a continuación, hacer las divisiones de mayor a menor. Cada potencia sólo necesitan ser considerados una vez.

Incluso entonces, puede ser mejor no construir potencias de 10 que no cabe en la palabra de máquina, y no repite la división por (pequeños poderes de) 10.

También, esto suena ahora más como la programación de matemáticas, así que lo siento.