¿Alguien sabe de un algoritmo o fórmula para convertir entre y arbitrario base $n$ % otra base $m$?
Respuestas
¿Demasiados anuncios?
Gudmundur Orn
Puntos
853
Esto es a menudo llamado "la Conversión de la Base" o "Cambio de Base". Usted puede leer sobre él aquí y aquí. Y cualquiera que apoye el Nuevo programa de Matemáticas probablemente se sienten de repente reforzados por esta pregunta. ;p
Por el camino, ya que es bastante fácil trabajar con la base 10 con la mano, casi me sospecho que la mayoría de tales algoritmos de convertir primero a base 10 (no es tan malo, solo multiplicar) y, a continuación, convertir a la nueva base de que la división se hace en base 10 (sólo divide a cabo diferentes poderes de la nueva base para obtener la nueva representación).
\begin{align} f(\color{red}{a_ma_{m-1}\ldots a_2a_1}, \color{blue}{b_nb_{n-1}\ldots b_2b_1}) &= f(\color{red}{a_ma_{m-1}\ldots a_2}, \color{blue}{b_nb_{n-1}\ldots b_2}) \color{blue}{b_1}\color{red}{a_1} \\ f(\color{red}{\varepsilon}, \color{blue}{b_nb_{n-1}\ldots b_2b_1}) &= f(\color{red}{\varepsilon}, \color{blue}{b_nb_{n-1}\ldots b_2}) \color{blue}{b_1}\color{red}{0} \\ f(\color{red}{a_ma_{m-1}\ldots a_2a_1}, \color{blue}{\varepsilon}) &= f(\color{red}{a_ma_{m-1}\ldots a_2a_1}, \color{blue}{\varepsilon}) \color{blue}{0}\color{red}{a_1} \\ f(\color{red}{a_1}, \color{blue}{\varepsilon}) &= \color{blue}{\varepsilon}\color{red}{a_1} \\ f(\color{red}{\varepsilon}, \color{blue}{\varepsilon}) &= \varepsilon \end-EDITAR\begin{align} \color{red}{0},\color{blue}{50} &\to \color{blue}{5}\, \color{red}{0}\, \color{blue}{0}\, \color{red}{0}\,,\\ \color{red}{50},\color{blue}{0} &\to \color{red}{5}\, \color{blue}{0}\, \color{red}{0}. \end---
Ok, vamos a hacer un par de ejemplos que puede utilizar para extraer un algoritmo. Afortunadamente, la conversión de 16 a 256 o 1024 es increíblemente fácil. Realmente, super fácil. Pero voy a hacer una conversión general y, a continuación, el que desee.
Voy a utilizar el $( \cdot )_b$ la notación significa que el número de $ \cdot$ en base b.
Así que supongamos que tenemos el número Hexadecimal $(1C2E)_{16}$ y queremos convertir esto en base 256. Una manera de hacerlo es convertir primero a decimal. Así que hacer: $$(1C2E)_{16} = 14 + 2 \cdot 16 + 12 \cdot 16^2 + 1 \cdot 16^3 = (7214)_{10}$$ Ahora que la tenemos en decimal, podemos tirar en base 256 por división. $$\lfloor7214/256 \rfloor= 28 \quad ;\quad 7214 \mod {256} = 46$$ Así que nuestro número escrito en base 256 es $(28,46)_{256}$, donde 28 significa que cualquiera que sea el símbolo que utilizamos para la 28 y 46 es el símbolo de 46, igual que Un 10 en Hexadecimal. La coma separa las posiciones.
El afortunado parte acerca de esta conversión es que aunque $16^2 = 256$. Así que sólo podemos ver en nuestra notación Hexadecimal en bloques de 2 dígitos, y convertirlos. Esto es genial! Por lo $1C2E$ puede dividirse en $1C$$2E$. Bien, $2E = 2*16 + 14 = 46$$1C = 1*16 + 12 = 28$. 28 y 46 de nuevo! Así que la base de 256 uno se encuentra escrito como 28,46!
Escribiendo esto en base a 1024 es más molesto. Recomiendo que se convierte en base 10 y, a continuación, a base de 1024 utilizando el algoritmo sugerido anteriormente. Si eres valiente, puedes hacerlo mucho más rápido mediante la conversión a binario y luego de la conversión de binario. ¿Por qué es tan bueno? Como base 16 es una potencia de 2, y a 1024 es una potencia de 2, las representaciones binarias no sangran,' es decir, los bloques de dígitos puede ser considerada sin preocuparse por sus vecinos.
Por ejemplo, 1 en binario es 1. C es 8 + 4, y así 1100. 2 es de 10. E es C + 2, por lo que es de 1110. Por lo $(1C2E)_{16}=(1110000101110)_2$. Para convertir a base de 256, ya que $2^8 = 256$, usted acaba de tomar de 8 dígitos al mismo tiempo. Los últimos 8 dígitos son 00101110, y este es de 46. Los otros son 11100, que es de 28. Eso es útil, y de hecho muy, muy rápidamente en un equipo.
Tomando nota de que $2^{10} = 1024$, se puede tomar de 10 dígitos de las secciones de la representación binaria de escribir en la base. Los últimos 10 dígitos son, sorprendentemente suficiente, 0000101110. Esto todavía pasa a ser de 46 años, debido a un divertido elección de mi número. El próximo 10 dígitos son 111, que es 7. Así que en base a 1024, fue escrito como $(7,46)_{1024}$.
Eso es todo lo que hay escrito.
David HAust
Puntos
2696
Considerando la base de la notación en anidados Horner forma lleva a una evidente algoritmo recursivo en el dígito de la lista de $\rm\: [d_0,d_1,\cdots,d_k]\:$ $\rm\: d_0 + n\:(d_1 + n\:(d_2 + \cdots + d_k))\:$ en radix $\rm\:n\:.\:$ es decir, de forma recursiva calcular el radix $\rm\:m\:$ en la representación de la cola $\rm\:[d_1,d_2,\cdots,d_k]\:,\:$, entonces, el empleo de radix $\rm\:m\:$ operaciones, se multiplica por $\rm\:n\:$ y añadir $\rm\:d_0\:,\:$ después de la conversión, tanto para radix $\rm\:m\:.\:$ Dijo que más sucintamente
$$\rm [d_0,d_1,\cdots,d_k]^{(n\ \mapsto\ m)}\ =\:\ d_0^{(n\ \mapsto\ m)}\ +\ n^{(n\ \mapsto\ m)}\ *\ [d_1,d_2,\cdots, d_k]^{(n\ \mapsto\ m)}$$
Desenrollar esta recursividad, esto equivale a la aplicación de la operación de conversión de $\rm\:(\ \ )^{\ (n\ \mapsto\ m)}\:$ a todos los términos en el completamente expandida Horner forma señalada anteriormente. Tenga en cuenta que esta conversión mapa de desplazamientos con $+$ $*$ porque es un anillo de isomorfismo de los números enteros representados en radix $\rm\:n\:$ a los números enteros representados en radix $\rm\:m\:$. Uno es esencialmente el uso de este isomorfismo a la estructura de transporte entre los anillos - aquí de la estructura en el polinomio de la forma que está implícito en la base de la representación.
Varias optimizaciones son posibles. Por ejemplo, para fijo $\rm\:n > m\:$ uno puede precompute una tabla de asignación de los dígitos en base $\rm\:n\:$ a su radix $\rm\:m\:$ conversiones. Tenga en cuenta también que si $\rm\: m = n^k\:$, la conversión es trivialmente logra mediante la división en trozos de $\rm\:k\:$ dígitos.
Paul Rapoport
Puntos
11
