Dlaczego mnożenie jest szybsze od dzielenia?

Hej,

Robiłem ostatnio benchmark w pythonie dla prostego dzielenia i mnożenia jednej danej liczby odpowiednio przez 2 oraz przez 0.5 i różnica (czas wykonania) była dość znaczna, bo oscylowała wokół 30% na korzyść mnożenia. Zdaję sobie sprawę, że to zależy również w sporej mierze np. od VM itd., ale ciekawi mnie sama istota funkcji dzielenia i mnożenia przez procek. Pytanie pierwsze: dlaczego dzielenie jest wolniejsze od mnożenia? Pytanie drugie: jak się odbywa jedno i drugie? Pytanie trzecie: czy dzielenie liczby całkowitej przez liczbę całkowitą różni się (funkcyjnie) od mnożenia liczby całkowitej przez ułamek?

Będę wdzięczny za wasze odpowiedzi i polecenie jakichś ewentualnych materiałów do poczytania.

Pozdrawiam.

A porównaj sobie mnożenie i dzielenie na kartce - właśnie dlatego.
Procesor robi to prawie dokładnie tak samo.

1. Wykonaj sobie na kartce mnożenie i dzielenie pisemne i zobacz które jest trudniejsze :P
2. Mnożenie czy dzielenie przez 2 dla integerów to słaby przykład bo wymaga tylko przesunięcia bitów w prawo albo w lewo...
3. Nie bardzo rozumiem pytanie "jak się to odbywa". Procesor / koprocesor mają instrukcje mul i div które to robią. Chyba że pytasz na jeszcze niższym poziomie? Mnożenie to na przykład kilka ANDów i ORów ;]
4. Operacje ułamkowe się różnią bo korzystają z koprocesora no i ułamki mają zupełnie inną, bardziej skomplikowaną reprezentację binarną.

Shalom napisał(a)

2. Mnożenie czy dzielenie przez 2 dla integerów to słaby przykład bo wymaga tylko przesunięcia bitów w prawo albo w lewo...

Rozwinę Twoją wypowiedź - mnożenie czy dzielenie przez potęgi dwójki dla liczb całkowitych to odpowiednie przesunięcie bitowe w lewo (dla mnożenia) lub w prawo (dla dzielenia) o odpowiednią ilość bitów; Choć powinno się to robić samemu w kodzie (co zmniejsza nieco czytelność), to za zapominalskich zrobi to optymalizator (pod warunkiem, że optymalizacja jest włączona w opcjach kompilacji).

Pytanie pierwsze: dlaczego dzielenie jest wolniejsze od mnożenia?

Przyczyna jest zupełnie inna niż napisali przedmówcy: podstawowym problemem dla którego mnożenie na procesorze jest wielokrotnie szybsze (nie 30% szybsze ale dziesiątki razy szybsze; dla przykładu na procesorach Intel Haswell: mnożenie ma opóźnienie 3 cykle dla 64-bitowych liczb, dzielenie ma maksimum 103 cykle opóźnienia) jest to, że mnożenie się łatwo zrównolegla, a dzielenie trudno.

Dla przykładu mnożenie 64 bity x 64 bity można rozbić na 8 mnożeń 64 bity x 8 bitów, a następnie 7 dodawań. Te dododawania też można ttochę zrównoleglić układając je w drzewo dodawań - wtedy wystarczy tyle kroków ile wynosi głębokość drzewa - tutaj 3 kroki.

Pytanie drugie: jak się odbywa jedno i drugie?

To jest mocno zależne od implementacji. Ale Wikipedia jest twoim przyjacielem:
http://en.wikipedia.org/wiki/Multiplication_algorithm
http://en.wikipedia.org/wiki/Division_algorithm

Pytanie trzecie: czy dzielenie liczby całkowitej przez liczbę całkowitą różni się (funkcyjnie) od mnożenia liczby całkowitej przez ułamek?

Nie wiem o co chodzi z tym funkcyjnie, ale logiczne jest, że dzielenie liczb całkowitych nie wymaga operowania na floatach, a co za tym idzie odpada mnóstwo sytuacji szczególnych (NaNs, denormals, nieskończoności, itd). Jak już napisałem wcześniej - mnożenie jest zdecydowanie szybsze na chyba wszystkich możliwych procesorach które dzisiaj są sprzedawane.

Możenie, zarówno na integerach jak i floatach jest zwykle sporo szybsze niż dzielenie - także zarówno na integerach jak i floatach. Mówię tutaj o CPU, w których nie szkoda tranzystorów na to by uzyskiwać wysoką wydajność jednowątkową. W przypadku GPU (przynajmniej Radeonów) jest tak, że priorytetem są floaty i np mnożenie floatów 32-bit (przypominam: mantysa jest tam 24-bitowa) jest tak samo szybkie jak mnożenie intów 24-bitowych, ale już mnożenie intów 32-bitowych wymaga programowej emulacji lub innych metod znacząco wolniejszych od prostego mnożenia.

PS:
Tabele z opóźnieniami poszczególnych instrukcji na różnych architekturach masz np tutaj: http://agner.org/optimize/instruction_tables.ods

Super! Bardzo Wam dziękuję za odpowiedzi :) Pora się trochę pouczyć.