Dlaczego podział jest droższy niż mnożenie?

Question

Nie próbuję niczego optymalizować, ale pamiętam, że słuchałem tego od programistów przez cały czas, że uznałem to za prawdę. W końcu powinni wiedzieć o tym.

Ale zastanawiam się, dlaczego podział jest wolniejszy od mnożenia? Czy podział nie jest po prostu uwielbionym odejmowaniem, a mnożenie jest gloryfikowanym dodatkiem? Więc matematycznie nie rozumiem, dlaczego przejście w jedną lub w drugą stronę ma bardzo różne koszty obliczeniowe.

Czy ktokolwiek może wyjaśnić przyczyny/przyczyny tego, więc wiem, zamiast tego, co usłyszałem od innych programistów, o które prosiłem, przed którym jest: "ponieważ".

Answer 1

Jednostka CPU ALU (jednostka arytmetyczno-logiczna) wykonuje algorytmy, chociaż są one implementowane sprzętowo. Algorytmy klasycznych multiplikacji obejmują Wallace tree i Dadda tree. Więcej informacji jest dostępnych here. Bardziej wyrafinowane techniki są dostępne w nowszych procesorach. Ogólnie rzecz biorąc, procesory starają się zrównoważyć operacje bitów, aby zminimalizować wymagane cykle zegara. Algorytmy mnożenia można dość skutecznie zrównoleglić (chociaż potrzeba więcej tranzystorów).

Division algorithms nie można zsynchronizować tak wydajnie. Najbardziej wydajne algorytmy podziału są dość złożone (The Pentium FDIV bug demonstruje poziom złożoności). Zasadniczo wymagają więcej cykli zegara na bit. Jeśli szukasz więcej szczegółów technicznych, here to miłe wyjaśnienie od firmy Intel. Intel faktycznie patented ich algorytm podziału.