Como funciona a multiplicação e a divisão na CPU?

Existem vários métodos diferentes de multiplicação, mas a maioria deles, na base, utiliza algum tipo de tabela de pesquisa. Isto é - se você é de uma certa idade - da mesma forma que as crianças na escola foram ensinadas suas tabelas de multiplicação -

"uma vez dois são dois, dois dois dois são quatro, três dois são seis ..."

Quando você precisa multiplicar 5 por 8, você não trabalha - você só se lembra "cinco oitos são 40". Ou pelo menos, eu lembro-me. Os jovens whippersnappers de hoje provavelmente usam a calculadora no seu telefone.

Em binário, há 256 resultados possíveis de 8 bits a partir da multiplicação de dois números binários de 4 bits. 256 bytes é um tamanho conveniente para uma tabela de pesquisa codificada com todos os resultados possíveis, assim uma CPU pode multiplicar dois números de 8 bits dividindo cada um deles em dois números de 4 bits, procurando os quatro produtos 4x4 parciais e adicionando-os, com variações de 4 bits de compensação, para produzir o produto de 16 bits. Isto é muito rápido. CPUs maiores podem ter o espaço necessário para fazer tabelas de pesquisa maiores - uma tabela de multiplicação de 8 por 8 requer 65.536 palavras de 16 bits (131kB). Acima de 8 por 8, as mesas se tornam invariavelmente grandes. As fichas mais pequenas podem usar uma tabela 2x2 com mais estágios de adição. Também seria possível fazê-lo em microcódigo, usando o tradicional algoritmo shift-and-add, mas isso seria muito lento. Eu não conheço nenhum CPUs moderno que o faça dessa forma.

Divisão é muito mais difícil. Pode ser feito em lógica combinatória, como so:

Cada caixa quadrada contém uma dúzia de portões lógicos, como so -

Então um divisor de n bits precisa de n*n elementos que ocupam muito espaço. Consequentemente, a maioria das CPUs pequenas implementam-no em microcódigo usando o tradicional algoritmo shift-and-subtract, ou (mais tipicamente) omitem-no por completo. É somente quando você atinge as CPUs na escala de milhões de transistores que o método lógico se torna econômico.