Por que a divisão é mais cara que a multiplicação?

Eu não estou realmente tentando otimizar nada, mas lembro-me de ouvir isso de programadores o tempo todo, que eu tomei como verdade. Afinal, eles deveriam saber disso.

Mas eu me pergunto por que a divisão é realmente mais lenta que a multiplicação? A divisão não é apenas uma subtração glorificada, e a multiplicação é um acréscimo glorificado? Então, matematicamente, não vejo por que ir de um jeito ou de outro tem computacionalmente custos muito diferentes.

Alguém pode, por favor, esclarecer o motivo / causa disso, então eu sei, em vez do que eu ouvi de outro programador que eu perguntei antes, que é: “porque”.

A ALU da CPU (Arithmetic-Logic Unit) executa algoritmos, embora eles sejam implementados em hardware. Algoritmos de multiplicações clássicas incluem Wallace tree e Dadda tree . Mais informações estão disponíveis aqui . Técnicas mais sofisticadas estão disponíveis em processadores mais recentes. Geralmente, os processadores buscam paralelizar as operações de pares de bits para minimizar os ciclos de clock necessários. Os algoritmos de multiplicação podem ser paralelizados de forma bastante eficaz (embora sejam necessários mais transistores).

Os algoritmos de divisão não podem ser paralelizados de forma tão eficiente. Os algoritmos de divisão mais eficientes são bastante complexos ( o bug do Pentium FDIV demonstra o nível de complexidade). Geralmente, eles exigem mais ciclos de clock por bit. Se você está atrás de mais detalhes técnicos, aqui está uma boa explicação da Intel. A Intel patenteou seu algoritmo de divisão.