Cambio de base de un número natural

Detalles

Categoría: Programación

Publicado el Viernes, 09 Marzo 2007 10:10

Un número natural es un concepto (los naturales son aquellos enteros mayores o iguales que el cero). Un numero no se puede tocar ni comer, aunque nos sirve para contar y medir cosas que se tocan o se comen. No obstante, necesitamos una forma de representar ese concepto. En el mundo occidental utilizamos los dígitos  '0', '1', '2', '3', '4', '5', '6', '7', '8', y '9', introducidos por Leonardo de Pisa (Fibonacci) en la matemática occidental desde la matemática árabe junto con un sistema de representación posicional en base 10, o simplemente "decimal"... pero esa no es la única forma de representar un número.

En éste artículo vamos a reflexionar acerca de lo que significa representar un número en contraposición al concepto del propio número. Nos centraremos en el sistema de representación utilizando una base, como por ejemplo la decimal, y cómo construir un par de algoritmos que nos permitan trabajar con la representación en cualquier base del número. También hablamos acerca de los sistemas de numeración que se utilizan comunmente en informática: el binario y el hexadecimal (base 16).

Hay muchas formas de representar un número, pero estamos tan acostumbrados a tratar con el sistema decimal que a menudo confundimos el concepto de número con su representación gráfica.

Por ejemplo... piensa en el número 5. Yo también estoy pensando en él. Los dos tenemos ahora en nuestra cabeza el concepto de ese número... y para transmitirlo he tenido que utilizar un símbolo... éste:

5

Tú y yo conocemos el sistema decimal y por eso entiendes el concepto del número 5, pero podría haber utilizado otra simbología que ambos conozcamos... por ejemplo,

cinco

o esta, que utilizaban los romanos:

V

o cualquiera de éstas:

Aunque el símbolo cambie, el número sigue siendo el mismo. Los matemáticos hacen una distinción entre lo que llaman número y lo que llaman numeral. Mientras que el número es un concepto, el conjunto de símbolos que se utilizan para representarlo en sistema concreto es el numeral. Así pues, el símbolo "5" es un numeral que utilizamos junto con el sistema en base 10 o decimal. El número 5 es lo que tú y yo ahora mismo tenemos en la cabeza y representamos con el numeral "5".

Bueno, vale... hay distintas maneras de representar el número cinco, pero... ¿A qué viene este rollo?

Pues simplemente, porque aunque normalmente hablamos de "Cambiar de base un número" (como he hecho yo en el título de éste artículo), el número no cambia... simplemente, escogemos un método distinto para representarlo.

Sabemos que los ordenadores utlizan el binario para codificar los números... pero realmente, nosotros no podemos cambiar de base un número... sino representarlo en una base cualquiera... es decir... si nuestro compilador tiene un tipo para almacenar enteros (int, integer o similar), una variable de ese tipo contendrá un determinado número entero, que es totalmente independiente del sistema interno que el ordenador o el compilador utilicen para representarlo. Cuando nosotros utilizamos una orden para obtener la representación escrita de ese número, es entonces cuando se nos presentan las cifras que lo representan en base decimal. Quizá los ordenadores del futuro utilicen otro sistema distinto del binario para representar los naturales... Quizá un pequeño duende dentro de la CPU pintando rayitas... como éste:

Da igual... el caso es que cuando nosotros imprimamos por pantalla la representación del número que gestiona ese duende, nos saldra por pantalla un '1' y un '7... es decir, 17.

Así pues, el algoritmo de éste artículo, no va a cambiar la naturaleza de un entero, sino que va a obtener la representación en cualquier base de un número natural.

El sistema de bases es bien conocido por todos nosotros... lo utilizamos de manera muy intuitiva.  La representación decimal de los números que utilizamos corresponde a un sistema que llamamos posicional. En este sistema, cada dígito de la representación de un número toma un determinado valor que corresponde con su posición dentro de la representación. Hay otros sistemas que no son posicionales, por ejemplo, el que utiliza el duende de arriba.

Cuando utilizamos una base decimal (dicen que utilizamos esta base por el hecho de tener 10 dedos en las manos) a la hora de representar un número natural, lo escribimos como una serie de dígitos (del 0 al 9). Al dígito de más a la izquierda le llamamos "Dígito Más significativo", y al de la derecha, "Dígito Menos Significativo". Es decir, el más significativo tiene más valor debido a su posición, y el menos significativo menos valor.

En el sistema decimal, el valor real de un número se calcula sumando una serie de términos. Cada término esta formado por: el valor del dígito, multiplicado por 10 elevado a la posición que ocupa. Las posiciones se numeran desde el dígito menos significativo al más significativo. El dígito menos significativo se dice que es la posición 0... el de su izquierda la 1, el siguiente a la izquierda la 2... y así hasta llegar al más significativo.

Por ejemplo, si tomamos el número 7156 en decimal, el 6 está en la posición 0, el 5 en la posición 1, el 1 en la 2 y el 7 en la 3. Así pues, su valor es: 7·10³+1·10²+5·10¹+6·10⁰

Vale... Si nos dan la representación en decimal de un número, podemos saber cual es el valor de ese número... fantástico. Pues el mismo sistema nos vale para cualquier otra base... por ejemplo, si presento el número 15764 y te digo que está en base 8 ¿Qué número es realmente? (Ojo... la base 8 utiliza los dígitos 0 a 7)... te puedo decir una cosa, no es el quicemil setecientos sesenta y cuatro. (Nota: voy a poner la base como un subíndice tras el número: 15764₈ Si no pongo nada, es que estoy utilizando la base 10. Ésto se suele hacer a menudo en matemáticas). Bueno... Vamos a ver qué número es éste...

15764₈=1·8⁴+5·8³+7·8²+6·8¹+4·8⁰=7156

Anda... pero ¡si es el mismo! 15764₈ es la representación en base 8 del mismo número que 7156 en base 10.

Bueno... pues ya tenemos claro algo: Si un entero x se representa en base b con i dígitos en la forma X_i-1,_Xi-2... X₁X₀, su valor viene dado por la expresión

Esa expresión nos permitirá obtener un algoritmo tal que dada la representación en una base b de un número x podamos saber cuál es ese número.

Pero... ¿Y al revés? ¿Y si nos dan un número y tenemos que obtener su representación en una base cualquiera?. Vamos a verlo... Vamos a coger el mismo número de antes... el 7156

Si quisiera saber cuál es el dígito menos significativo de 7156 en base 10, simplemente tengo que dividir por 10 y quedarme con el resto de la división (también llamado módulo).

Es decir, si hallo el resto de la división de 7156 entre 10, me sale un 6. Pero si además, saco el cociente de la división entera, vale 715. Así pues, con la división entera y el módulo logramos separar por un lado el dígito menos significativo y por el otro, el resto de los dígitos. Si ahora repito la operación con el 715, logramos separar por un lado 71, y por otro el 5...

Recapitulando,

En la última división hemos obtenido un 0, y a partir de ahí ya no nos hace falta seguir. Los módulos nos han ido dando los digitos en base 10 que conforman a nuestro número, desde el menos significativo al más, y las divisiones nos han permitido ir realizando el proceso.

Pues este mismo proceso nos sirve para obtener la representación en cualquier base. Vamos a probar con el 7156 y con la base 8:

A ver que nos dan los restos.... 1,5,7,6,4....Es decir... ¡15764₈!

Pues ya lo tenemos... Con esta forma de actuar podemos obtener un algoritmo tal que dado un número natural nos dé su representación en cualquier base.

HEXADECIMAL, BINARIO y OCTAL

De entre todas las posibles bases que podamos utilizar, suelen ser especialmente comunes la representación en base 2 (binario), en base 16 (hexadeciamal) y en base 8 (octal).

En base 2 sólo se utilizan dos dígitos, el 0 y el 1. Es de interés porque, como ya sabemos, los ordenadores y otras máquinas digitales utilizan únicamente dos estados de señales eléctricas para representar prácticamente cualquier cosa que necesitan. Si uno de esos estados se asocia al dígito 0 y el otro al 1... pues resulta que en binario se puede representar casi cualquier cosa.

La base 16 (hexadecimal), tiene interés porque 16 es una potencia de 2 (concretamente es 2⁴). Eso dota a las representaciones en hexadecimal de una curiosa propiedad: cuatro cifras en base 2 se corresponden con una en base 16 y hace que podamos pasar de base 2 a 16 y viceversa prácticamente "de cabeza". Además, supone un ahorro a la hora de escribir tiras de bits, y reduce considerablemente la posibilidad de error. Los ordenadores trabajan en base 2, pero los humanos que trabajamos con ordenadores utilizamos la base 16 para comunicarnos entre nosotros debido a este paralelismo con la base 2. También viene muy bien poque por convención, los bits se agrupan en un ordenador en grupos de 8 (un byte). Así pues, cada byte puede representarse con dos dígitos de la base 16.

En base 16 hacen falta 16 dígitos. Como nosotros nos manejamos normalmente sólo con 10, se decidió que los otros seis dígitos que hacen falta fueran las letras A, B, C, D, E y F.

Así pues, cada uno de los 16 dígios hexadecimales se corresponde con un grupo de 4 bits.

El fundamento para trabajar con la base 16 es el mismo que el que hemos comentado en la página anterior, aunque en el caso concreto de pasar de una representación en base 2 a una en base 16 y viceversa se pueden tomar algunos atajos basándonos en ese paralelismo que decíamos más arriba.

En cuanto a la base octal es una reminiscencia del pasado. Cada vez está más en desuso. El motivo por el que se utilizó es el mismo que el de la base 16... Al ser 8 una potencia de 2 (concretamente, 2³) tres bits pueden representarse con un sólo dígito de base 8.

El motivo por el que se utilizó en el pasado es, probablemente, que antes un byte tenía sólo 7 bits (bueno, realmente tenían 8, pero sólo se utilizaban 7... el octavo se utilizaba para comprobar la paridad de los otros 7). En ese caso, la base 8 era igual de incómoda que la base 16... pero con 8 bits por byte, como en los ordenadores actuales, la base 16 es mucho más cómoda.

ALGORITMO: De cualquier base a su valor.

Con todo lo que sabemos hasta ahora, ya podemos obtener un par de algoritmos, pero antes tenermos que decidir un alguna que otra cosa.

El primero de nuestros algoritmos aceptará como entrada la representación de un número natural en cualquier base y la propia base en la que está representado, y devolverá un entero con el valor del número representado.

Debemos decidir por un lado cuál va a ser la base máxima que aceptemos. En este caso va a ser la 16, pero puedes adaptar fácilmente el algoritmo a cualquier otra. El motivo es que debemos tener claros cuáles van a ser los dígitos que utilicemos. Por otro lado, nuestro algoritmo debería comprobar que la representación del número natural que se acpete como entrada sea válida. Si la base o la representación del entero no son válidos, deberíamos indicarlo de alguna manera, para evitar que se produzca GIGO o que el algoritmo falle. Como vamos a devolver un entero y sólo vamos a trabajar con naturales, devolveremos un -1 en caso de que los datos de entrada no sean válidos.

Para la representación del dato de entrada, necesitamos una tira de dígitos, así que como tipo de datos escogeremos una cadena.

A continuación, una descripción en pseudocódigo del algoritmo y una implementación sencilla en C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

//n=representación de un entero en una base
//b=base en la que está representado
//devuelve un entero mayor que 0 si la conversión se
//realiza correctamente, y -1 en otro caso
funcion CualquierBaseAEntero(n:cadena, base: entero):entero
variables: 
   p:entero; //posicion
   i:entero;
   resultado:entero=0;
empieza
   Comprobar que 2<=base<=16 y que n es una
     representación válida para esa base.
     Si no es así, devolver -1 y terminar.
   para p desde 0 hasta tamaño(n)-1 hacer
      i=valor del dígito en posicion tamaño(n)-1-p
      resultado=resultado+i*base^p
   fin para
   devolver resultado
termina

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

//n=representación de un entero en una base
//b=base en la que está representado
//devuelve un entero mayor que 0 si la conversión se
//realiza correctamente, y -1 en otro caso
int CualquierBaseAEntero(String n, int b)
{
   //Utilizaremos una cadena para
   //almacenar los dígitos. La posicion en
   //esta cadena nos da el valor de cada
   //dígito
   String digitos = "0123456789ABCDE";
   int resultado = -1;
   //comprobar que la base es válida
   if (b >= 2 && b <= 16)
   {
      resultado = 0;
      //comprobar que n es válido en base b
      //lo haremos a la vez que intentamos convertir
      int p = 0;
      //nos mantendremos en el bucle mientras que
      //no hayamos acabado y los dígitos que encontremos
      //sean válidos en base b
      while (p <n.Length && resultado >= 0)
      {
         int i = digitos.IndexOf(n[n.Length-1-p]);
         if (i >= 0 & i<b) //es un dígito válido
         {
            resultado += i * (int)Math.Pow(b,p);
         }
         else
         {
            resultado = -1;
         }
         p++;
      } //while
   }//if
return resultado;
}

{mospagebreak title=Algoritmo: De natural a cualquier base}

ALGORITMO: DE UN VALOR NATURAL A SU REPRESENTACIÓN EN CUALQUIER BASE

El segundo de nuestros algoritmos realizará la operación contraria a la anterior. Es decir, aceptará un número entero y la base en la que lo queremos representar, y devolverá una cadena con la representación en esa base.

Nuevamente tenemos que decidir un par de cosas. Primeramente, las bases con las que trabajaremos. En principio serán las mismas: cualquiera entre 2 y 16, pero el algoritmo es el mismo para cualquier otra base, basta definir los símbolos que se utilizarán.

Por otro lado, si los parámetros de entrada no son correctos, evitaremos el gigo o que el algortimo falle comprobándolo.  En este caso, si la base proporcionada no está entre 2 y 16, lo señalizaremos devolviendo una cadena vacía.

Vamos con el algoritmo, y con una implementación sencilla en C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

//i=el natural a representar en otra base
//b=la base en la que lo queremos representar
//devuelve una cadena no vacía si la conversión
//es correcta, y una vacía si los parámetros
//de entrada no son válidos
funcion EnteroACualquierBase(i:entero, b:entero):Cadena
variables:
   resultado:Cadena
   x:entero
empieza
   Comprobar que la base es válida y si no es
     así, devolver cadena vacía.
   Comprobar que i es mayor que 0
     Si no es así devolver "0" en caso de que
     i sea exactamente 0, y cadena vacía si es
     menor que 0
   resultado=""
   x=i //para no perder i
   mientras (x>0) hacer
     concatenar a la izquierda de resultado el dígito
       que corresponde con x mod b
     x=x/b
   fin mientras
   devolver resultado
termina

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

String EnteroACualquierBase(int i, int b)
{
   const String digitos = "0123456789ABCDE";
   String resultado;
   //si i es 0, el resultado será "0"
   resultado = (i == 0) ? "0" : "";
   //si la base es correcta
   if (b >= 2 && b <= 16 && i>0)
   {
      int x = i;
      while (x > 0)
      {
         //añadir el digito correspondiente al
         //resultado por la izquierda
         resultado = digitos[x % b] + resultado;
         //dividir y seguir
         x = x / b;
      }//while
   }//if
return resultado;
}

OPTIMIZACIONES

Estos algoritmos son un simple ejemplo para ilustrar el cambio de base, y son susceptibles de ser mejorados, especialmente el primero.

En el caso del primer algoritmo, hemos utilizado una cadena para representar los dígitos, y en cada vuelta del bucle hacemos una búsqueda en la cadena. Aunque hemos utilizado un método de librería (IndexOf), la lógica nos dice que probablemente ese método tenga un coste lineal, con lo que el algoritmo tendra un coste ∈ O(n·b) siendo n el tamaño de la cadena de entrada y b la base. Esto en principio no es grave, ya que la cadena de entrada y la base son, en general bastante pequeñas, pero si se va a realizar un uso intensivo del algoritmo quizá se podría mejorar.

El segundo algoritmo es bastante mejor, ya que su complejidad es logarítmica con respecto al entero que se le proporciona. Por cierto, la base de ese logaritmo es precisamente la base que se proporciona como entrada.

En el caso particular de pasar de base 2 a base 16, se pueden construir un par de algoritmos mucho más directos, ya que cuatro dígitos binarios se corresponden con uno hexadecimal y viceversa.

• < Previo
• Siguiente >