¡OJO! Si no eres informático o estudiante de ingenieria computacional, probablemente este artículo no te interese.

Hace unos días necesité implementar el algoritmo de Booth en C++ para una parte de una de las prácticas de la asignatura Teoría de autómatas y lenguajes formales y la verdad, aunque existe bastante información, eché en falta una explicación didáctica para comprender el procedimiento desde un punto de partida. Asi pues, en este artículo intentaré explicar el procedimiento del algoritmo lo mejor posible.

El algoritmo de Booth es un método rápido y sencillo para obtener el producto de dos números binarios con signo en notación complemento a dos.

Debemos saber que un número binario está formado por bits de ceros y unos, y que se puede traducir a decimal fácilmente de la siguiente forma:

Sabiendo que la posición de cada bit es 2^n (elevado a n) y partimos de n=0 de derecha a izquierda, sólo queda realizar la suma total de multiplicar por dicho bit, en este caso:
(0·2^7+1·2^6+0·2^5+1·2^4+0·2^3+1·2^2+1·2^1+0·2^0 = 86).

También debemos saber que el complemento a uno de un número binario es cambiar sus ceros por unos, y sus unos por ceros (complementar): (010010 -> ca1: 101101) y que el complemento a dos de un número binario es el resultado de sumar 1 al complemento a uno de dicho número binario:

Realizar una suma con dos números binarios es tarea fácil, pero la multiplicación resulta algo más complicada. Con el algoritmo de Booth, resulta mucho más sencillo de implementar. Partimos del ejemplo de la multiplicación 6·2=12:

Como se puede ver en la imagen superior, partiendo de los números binarios de la multiplicación 6·2 (multiplicando y multiplicador) creamos tres nuevos números binarios del doble de tamaño (16 en el ejemplo): A, S y P.

Partiendo del número P (producto) comenzamos a comparar los últimos 2 bits de la derecha, siguiendo los casos base del recuadro:

Se realizará esta comparación 8 veces en este ejemplo (número de bits de los operandos) y al final de cada comparación, realizamos un desplazamiento de un bit hacia la derecha, manteniendo el último bit de la izquierda, y descartando el último bit del lado contrario. Si hacemos una traza paso a paso nos quedarían los siguientes resultados:

Finalmente obtenemos el número en binario resultante (12 en este ejemplo), descartando el bit extra que hemos añadido al principio del procedimiento y que se encuentra en el extremo a la derecha.

Espero que esto les sirva tanto como me sirvió a mi en su momento.

Volviendo hacia atrás en el blog algunas semanas -haciendo backtracking-, comentaba el uso de la recursividad en la programación y lo interesante que resultaba definir algo contenido en la misma definición.

El Backtracking es una técnica de programación de la que se puede partir de la definición de Recursividad (vease definición de recursividad) con la diferencia que, en el backtracking, al existir varios caminos diferentes a elegir, una vez llegado al final y no cumplirse la condición establecida, volvemos atrás para seguir buscando caminos diferentes o alternativos y posiblemente correctos.

La idea del backtracking, si aún no la has entendido, se ve bastante bien en estos ejemplos del Laberinto y las n-Damas (en Java).

Finalmente, como lo prometido es deuda, subo la práctica comentada en el anterior artículo sobre recursividad que resuelve sudokus planteados por medio de la técnica del backtracking. Recordar que no es la mejor técnica ni mucho menos para resolver Sudokus, sino prácticamente usar la fuerza bruta para resolverlos con la posibilidad de volver atrás y buscar más caminos.

El programa está realizado para Free Pascal y permite:

• Insertar números uno a uno (comprobando si es posible insertar el número según las reglas)
• Cargar y salvar en un fichero de tipo propio los sudokus creados
• Intentar resolver el sudoku mediante backtracking indicandote si tiene varias, única o ninguna solución y calculando el tiempo que tarda en resolverlo.
• Borrar el sudoku actual del panel
• Insertar un sudoku predefinido por coordenadas (ojo! este no comprueba si los números son válidos).

Hay bastante cosas que son mejorables, como por ejemplo quitar algunas variables globales o la inclusión de eliminar algunos números insertando un cero (por ejemplo), pero eso lo dejo para el que quiera modificarlo, asi como el que se anime y lo «traduzca» a otro lenguaje de programación estaré encantado en incorporarlo al artículo.

Programa para resolver sudokus en Free Pascal con algunos ficheros de ejemplo.