performance - tipo - ¿Por qué la división es más costosa que la multiplicación?

método de multiplicación hindú o de celdillas o de gelosia

Question

Realmente no estoy tratando de optimizar nada, pero recuerdo haber escuchado esto de los programadores todo el tiempo, que lo tomé como una verdad. Después de todo se supone que deben saber esto.

Pero me pregunto por qué la división es realmente más lenta que la multiplicación. ¿La división no es solo una resta glorificada, y la multiplicación es una adición glorificada? Así que, matemáticamente, no veo por qué ir de una manera u otra tiene costos computacionalmente muy diferentes.

¿Alguien puede aclarar la razón / causa de esto, así que sé, en lugar de lo que escuché de otros programadores, que pregunté antes cuál es "porque".

Answer 1

La ALU la CPU ( ALU aritmético-lógica) ejecuta algoritmos, aunque se implementan en hardware. Los algoritmos de multiplicaciones clásicas incluyen el árbol Wallace y el árbol Dadda . Más información está disponible here . Técnicas más sofisticadas están disponibles en procesadores más nuevos. En general, los procesadores se esfuerzan por paralelizar las operaciones de pares de bits para minimizar los ciclos de reloj requeridos. Los algoritmos de multiplicación se pueden paralelizar de manera bastante efectiva (aunque se requieren más transistores).

Los algoritmos de división no se pueden paralelizar de manera eficiente. Los algoritmos de división más eficientes son bastante complejos ( el error Pentium FDIV demuestra el nivel de complejidad). En general, requieren más ciclos de reloj por bit. Si buscas más detalles técnicos, here hay una buena explicación de Intel. Intel realmente patented su algoritmo de división.