Hay varios métodos de multiplicación diferentes, pero la mayoría de ellos, en la base, usan algún tipo de tabla de búsqueda. Esto es, si tienes cierta edad, de la misma manera que a los niños en la escuela se les enseñó sus tablas de multiplicar:
“Una vez que dos son dos, dos son cuatro, tres son seis …”
Cuando necesita multiplicar 5 por 8, no lo resuelve, solo recuerda que “cinco ochos son 40” . O al menos lo hago. Los jóvenes whippersnappers de hoy probablemente usan la aplicación de calculadora en su teléfono.
- ¿Cómo harías para probar que un grupo no es cíclico?
- ¿Cuál es la potencia más grande de 2 en 32! +33! +34! +35! +… + 90 !?
- ¿Cómo se determina el cálculo de un recuento mínimo de un micrómetro?
- ¿Cómo se pueden encontrar los coeficientes impares en la expansión bionominal de (x + 1) ^ 1000 o incluso potencias más altas?
- ¿Qué es una explicación intuitiva de un álgebra de factorización?
En binario, hay 256 posibles resultados de 8 bits al multiplicar dos números binarios de 4 bits. 256 bytes es un tamaño conveniente para una tabla de búsqueda codificada con todos los resultados posibles, por lo que una CPU puede multiplicar dos números de 8 bits dividiendo cada uno de ellos en dos números de 4 bits, buscando los cuatro productos parciales 4 × 4 y agregándolos, con compensaciones variables de 4 bits, para producir el producto de 16 bits. Esto es muy rapido. Las CPU de matriz más grandes pueden permitir el espacio para hacer tablas de búsqueda más grandes: una tabla de multiplicación de 8 por 8 requiere 65.536 palabras de 16 bits (131kB). Por encima de 8 × 8, las tablas se vuelven inviablemente grandes. Los chips más pequeños pueden usar una tabla 2 × 2 con más etapas sumadoras. También sería posible hacerlo en microcódigo, utilizando el algoritmo tradicional shift-and-add, pero eso sería muy lento. No conozco ninguna CPU moderna que lo haga de esa manera.
La división es mucho más difícil. Se puede hacer en lógica combinatoria, así:
Cada una de las cajas cuadradas contiene una docena de puertas lógicas, así:
Por lo tanto, un divisor de n bits necesita n * n elementos que ocupan mucho espacio. En consecuencia, la mayoría de las CPU pequeñas lo implementan en microcódigo utilizando el algoritmo tradicional de desplazamiento y sustracción, o (más típicamente) lo omiten por completo. Solo cuando se alcanzan las CPU a escala de millones de transistores, el método lógico se vuelve económico.