Quiero contarles a los lectores sobre un truco de programación que conocí en algún tipo de libro de traducción que contiene una selección de esos trucos en aquellos días en que aún no se había inventado no solo el byte, sino que da miedo decir la pila, y el gran Dijkstra aún no maldijo al operador GOTO (sic, en mayúsculas).
Me gustó tanto el truco por su simplicidad y gracia que ya en este milenio me complació contarles a los estudiantes sobre él en la forma de la siguiente tarea.
Imagine que en el proceso de regresar de la Luna en 2030, de repente descubrió que su computadora de a bordo no está realizando correctamente las operaciones de multiplicación de enteros, y esto seguramente conducirá a un accidente durante el aterrizaje.
En esta historia no hay nada particularmente fantástico. Recordemos, por ejemplo, qué problemas ocurrieron una vez con
los procesadores Pentium , y para cuando lo enviaron a la luna, aún no había alcanzado la sustitución total de importaciones. En general, es necesario verificar si los procesadores fueron perforados especialmente.
Pero al punto. Necesita implementar urgentemente la multiplicación mediante programación para que funcione rápidamente en tiempo real y se ajuste a un recurso disponible.
Del curso de aritmética de la escuela, recordamos que los números de valores múltiples pueden multiplicarse por una columna, y el resultado de la multiplicación de números individuales puede tomarse de la tabla de multiplicación.
Pero solo si los números se eligen cortos (por ejemplo, 0 y 1), la tabla de multiplicación será corta y las columnas largas, y su cálculo llevará mucho tiempo.
Si, por el contrario, tomamos números largos (por ejemplo, de 0 a 65535), entonces para aritmética de 16 bits
el resultado se toma directamente de la tabla y faltan las columnas. Sin embargo, el tamaño de la tabla clásica de Pitágoras resulta ser de unos 17 GB (4 * 65536 * 65536), si tenemos en cuenta la simetría con respecto a la diagonal, la mitad es de unos 8,5 GB.
Puede ser un poco demasiado.
Apriete y recuerde álgebra.
(1)(2)Restar
(2) de
(1)y más
Por lo tanto, al tener una tabla de cuadrados en la matriz sqr, obtenemos
a * b = (sqr [a + b] - sqr [a - b]) / 4
(*)El tamaño de la tabla de 8 * (65535 + 65535) es de aproximadamente 8.4 MB, lo que ya puede ser aceptable.
El tamaño del elemento de la tabla de 8 bytes se debe al hecho de que para el máximo a y b, el cuadrado de su suma de 4 bytes no cabe: no hay suficientes 2 bits.
A continuación, describiré algunas mejoras, que no estaban en el libro. Se me ocurrió cuando ya estaba escribiendo esta nota.
Tenga en cuenta que los dos bits menos significativos de un cuadrado par siempre son 00, y el cuadrado impar siempre es 01. Por otro lado, para cualquier par de números, su suma y diferencia tienen la misma paridad.
Por lo tanto, en nuestra fórmula
(*), el proceso de sustracción entre paréntesis no puede tener guiones,
asociado con los dos bits menos significativos. Por lo tanto, el contenido de los elementos de la tabla de cuadrados.
Puede avanzar dos bits hacia la derecha y así ahorrar la mitad de la memoria.
Finalmente tenemos
a * b = sqr4 [a + b] - sqr4 [a - b]
(**)donde sqr4 es la tabla de cuadrados modificada.
En nuestro ejemplo, su tamaño es de aproximadamente 4,2 MB.
A continuación, para ilustrar este enfoque, se incluye el texto del programa Lua.
function create_multiplier(N)
Para los procesadores modernos, parece razonable tener un tamaño de dígito que sea un múltiplo del tamaño de byte para facilitar el acceso a ellos. Con dígitos de 1 byte, el tamaño de la tabla es de solo 1022 bytes, lo que puede permitir que este truco se use en procesadores de 8 bits que no tienen multiplicación de hardware.
Estaré agradecido a todos los lectores de esta nota por sus correcciones y comentarios.