Powinienem używać mnożenia czy dzielenia?

Oto głupie zabawne pytanie:

Powiedzmy, że musimy wykonać prostą operację, w której potrzebujemy połowy wartości zmiennej. Są zazwyczaj dwa sposoby osiągnięcia tego celu:

y = x / 2.0;
// or...
y = x * 0.5;

Zakładając, że używamy standardowych operatorów dostarczonych z językiem, który z nich ma lepszą wydajność?

Domyślam się, że mnożenie jest zazwyczaj lepsze, więc staram się tego trzymać, kiedy koduję, ale chciałbym to potwierdzić.

Chociaż osobiście jestem zainteresowany odpowiedzią na Python 2.4-2.5, nie krępuj się również opublikować odpowiedzi w innych językach! A jeśli chcesz, możesz również opublikować inne, bardziej wyszukane sposoby (na przykład użycie operatorów z przesunięciem bitowym).

Pyton:

time python -c 'for i in xrange(int(1e8)): t=12341234234.234 / 2.0'
real    0m26.676s
user    0m25.154s
sys     0m0.076s

time python -c 'for i in xrange(int(1e8)): t=12341234234.234 * 0.5'
real    0m17.932s
user    0m16.481s
sys     0m0.048s

mnożenie jest o 33% szybsze

Lua:

time lua -e 'for i=1,1e8 do t=12341234234.234 / 2.0 end'
real    0m7.956s
user    0m7.332s
sys     0m0.032s

time lua -e 'for i=1,1e8 do t=12341234234.234 * 0.5 end'
real    0m7.997s
user    0m7.516s
sys     0m0.036s

=> bez różnicy

LuaJIT:

time luajit -O -e 'for i=1,1e8 do t=12341234234.234 / 2.0 end'
real    0m1.921s
user    0m1.668s
sys     0m0.004s

time luajit -O -e 'for i=1,1e8 do t=12341234234.234 * 0.5 end'
real    0m1.843s
user    0m1.676s
sys     0m0.000s

=> to tylko 5% szybciej

wnioski: w Pythonie mnożenie jest szybsze niż dzielenie, ale gdy zbliżasz się do procesora za pomocą bardziej zaawansowanych maszyn wirtualnych lub JIT, przewaga znika. Jest całkiem możliwe, że przyszła maszyna wirtualna Pythona uczyniłaby to nieistotnym

Zawsze używaj tego, co jest najwyraźniejsze. Cokolwiek robisz, to próba przechytrzenia kompilatora. Jeśli kompilator jest w ogóle inteligentny, zrobi wszystko, co w jego mocy, aby zoptymalizować wynik, ale nic nie może sprawić, że następny facet nie będzie cię nienawidził za twoje gówniane rozwiązanie do przesuwania bitów (tak przy okazji, uwielbiam manipulację bitami, to fajne. Ale fajnie! = Czytelne )

Przedwczesna optymalizacja jest źródłem wszelkiego zła. Zawsze pamiętaj o trzech zasadach optymalizacji!

1. Nie optymalizuj.
2. Jeśli jesteś ekspertem, zapoznaj się z zasadą nr 1

3. Jeśli jesteś ekspertem i potrafisz uzasadnić taką potrzebę, zastosuj następującą procedurę:

   • Zakoduj niezoptymalizowany kod
   • określić, jak szybko jest „wystarczająco szybkie” - zwróć uwagę, które wymagania użytkownika / historia wymaga tych danych.
   • Napisz test szybkości
   • Przetestuj istniejący kod - jeśli jest wystarczająco szybki, gotowe.
   • Przekoduj to zoptymalizowane
   • Przetestuj zoptymalizowany kod. JEŚLI nie spełnia wymagań, wyrzuć go i zachowaj oryginał.
   • Jeśli spełni test, zachowaj oryginalny kod jako komentarze

Ponadto robienie rzeczy, takich jak usuwanie wewnętrznych pętli, gdy nie są one wymagane, lub wybieranie połączonej listy w tablicy do sortowania przez wstawianie, nie jest optymalizacją, tylko programowaniem.

Myślę, że robi się to tak dziwaczne, że lepiej byłoby zrobić wszystko, co czyni kod bardziej czytelnym. Jeśli nie wykonasz tych operacji tysiące, jeśli nie miliony razy, wątpię, by ktokolwiek kiedykolwiek zauważył różnicę.

Jeśli naprawdę musisz dokonać wyboru, benchmarking to jedyna droga. Znajdź funkcje, które powodują problemy, a następnie dowiedz się, gdzie w funkcji występują problemy i napraw te sekcje. Wciąż jednak wątpię, czy pojedyncza operacja matematyczna (choćby powtarzana wiele, wiele razy) byłaby przyczyną jakiegokolwiek wąskiego gardła.

Mnożenie jest szybsze, dzielenie dokładniejsze. Stracisz precyzję, jeśli twoja liczba nie jest potęgą 2:

y = x / 3.0;
y = x * 0.333333;  // how many 3's should there be, and how will the compiler round?

Nawet jeśli pozwolisz kompilatorowi obliczyć odwróconą stałą z idealną precyzją, odpowiedź może być inna.

x = 100.0;
x / 3.0 == x * (1.0/3.0)  // is false in the test I just performed

Problem z szybkością może mieć znaczenie tylko w językach C / C ++ lub JIT, a nawet wtedy, gdy operacja jest zapętlona w wąskim gardle.

Jeśli chcesz zoptymalizować swój kod, ale nadal jest jasny, spróbuj tego:

y = x * (1.0 / 2.0);

Kompilator powinien mieć możliwość dzielenia w czasie kompilacji, więc w czasie wykonywania otrzymujesz mnożenie. Spodziewałbym się, że precyzja będzie taka sama jak w y = x / 2.0kopercie.

Tam, gdzie może to mieć znaczenie, LOT znajduje się w procesorach wbudowanych, w których do obliczania arytmetyki zmiennoprzecinkowej wymagana jest emulacja zmiennoprzecinkowa.

Zamierzam tylko dodać coś dla opcji „inne języki”.
C: Ponieważ to jest tylko ćwiczenie akademickie, to naprawdę nie robi różnicy, pomyślałem, że wniesie coś innego.

Skompilowałem do assemblacji bez optymalizacji i spojrzałem na wynik.
Kod:

int main() {

    volatile int a;
    volatile int b;

    asm("## 5/2\n");
    a = 5;
    a = a / 2;

    asm("## 5*0.5");
    b = 5;
    b = b * 0.5;

    asm("## done");

    return a + b;

}

skompilowane z gcc tdiv.c -O1 -o tdiv.s -S

podział na 2:

movl    $5, -4(%ebp)
movl    -4(%ebp), %eax
movl    %eax, %edx
shrl    $31, %edx
addl    %edx, %eax
sarl    %eax
movl    %eax, -4(%ebp)

i pomnożenie przez 0,5:

movl    $5, -8(%ebp)
movl    -8(%ebp), %eax
pushl   %eax
fildl   (%esp)
leal    4(%esp), %esp
fmuls   LC0
fnstcw  -10(%ebp)
movzwl  -10(%ebp), %eax
orw $3072, %ax
movw    %ax, -12(%ebp)
fldcw   -12(%ebp)
fistpl  -16(%ebp)
fldcw   -10(%ebp)
movl    -16(%ebp), %eax
movl    %eax, -8(%ebp)

Jednak kiedy zmieniłem te intnadouble s (co prawdopodobnie zrobiłby Python), otrzymałem to:

podział:

flds    LC0
fstl    -8(%ebp)
fldl    -8(%ebp)
flds    LC1
fmul    %st, %st(1)
fxch    %st(1)
fstpl   -8(%ebp)
fxch    %st(1)

mnożenie:

fstpl   -16(%ebp)
fldl    -16(%ebp)
fmulp   %st, %st(1)
fstpl   -16(%ebp)

Nie testowałem żadnego z tego kodu, ale po zbadaniu kodu widać, że przy użyciu liczb całkowitych dzielenie przez 2 jest krótsze niż mnożenie przez 2. Używając podwójnych, mnożenie jest krótsze, ponieważ kompilator używa zmiennoprzecinkowych opkodów procesora, które prawdopodobnie działają szybciej (ale właściwie nie wiem) niż nie używam ich do tej samej operacji. Ostatecznie więc ta odpowiedź pokazała, że ​​wydajność mnożenia przez 0,5 w porównaniu z dzieleniem przez 2 zależy od implementacji języka i platformy, na której działa. Ostatecznie różnica jest znikoma i jest czymś, o co praktycznie nigdy nie powinieneś się martwić, z wyjątkiem czytelności.

Na marginesie, możesz zobaczyć, że w moim programie main()powraca a + b. Kiedy usuwam słowo kluczowe volatile, nigdy nie zgadniesz, jak wygląda zestaw (wyłączając konfigurację programu):

## 5/2

## 5*0.5
## done

movl    $5, %eax
leave
ret

wykonał zarówno dzielenie, mnożenie, jak i dodawanie w jednej instrukcji! Oczywiście nie musisz się tym martwić, jeśli optymalizator jest godny szacunku.

Przepraszam za zbyt długą odpowiedź.

Po pierwsze, jeśli nie pracujesz w C lub ASSEMBLY, prawdopodobnie jesteś w języku wyższego poziomu, w którym zastój w pamięci i ogólne koszty połączeń absolutnie przyćmiewają różnicę między mnożeniem i dzieleniem do punktu nieistotnego. Więc po prostu wybierz to, co w takim przypadku brzmi lepiej.

Jeśli mówisz z bardzo wysokiego poziomu, nie będzie to mierzalnie wolniejsze w przypadku niczego, do czego prawdopodobnie będziesz go używać. W innych odpowiedziach zobaczysz, że ludzie muszą wykonać milion mnożenia / dzielenia tylko po to, aby zmierzyć jakąś poniżej milisekundową różnicę między nimi.

Jeśli nadal jesteś ciekawy, z niskiego poziomu optymalizacji:

Potok dzielenia zwykle jest znacznie dłuższy niż mnożenia. Oznacza to, że uzyskanie wyniku zajmuje więcej czasu, ale jeśli potrafisz zająć procesor zadaniami niezależnymi, to nie kosztuje cię to więcej niż pomnożenie.

Długość różnicy w rurociągach jest całkowicie zależna od sprzętu. Ostatni sprzęt, którego użyłem, miał około 9 cykli dla mnożenia FPU i 50 cykli dla dzielenia FPU. Brzmi dużo, ale wtedy straciłbyś 1000 cykli z powodu utraty pamięci, dzięki czemu można spojrzeć z perspektywy.

Analogią jest umieszczenie ciasta w kuchence mikrofalowej podczas oglądania programu telewizyjnego. Całkowity czas, jaki zabrał ci z dala od programu telewizyjnego, to czas, w którym wstawiono go do kuchenki mikrofalowej i wyjąłeś z kuchenki mikrofalowej. Przez resztę czasu nadal oglądałeś program telewizyjny. Więc jeśli ciasto gotowało się 10 minut zamiast 1 minuty, w rzeczywistości nie zużywało więcej czasu na oglądanie telewizji.

W praktyce, jeśli chcesz osiągnąć poziom dbałości o różnicę między mnożeniem i dzieleniem, musisz zrozumieć potoki, pamięć podręczną, przestoje w gałęziach, prognozowanie poza kolejnością i zależności potoków. Jeśli to nie brzmi tak, jak zamierzałeś iść z tym pytaniem, to poprawną odpowiedzią jest zignorowanie różnicy między nimi.

Wiele (wiele) lat temu absolutnie konieczne było unikanie podziałów i zawsze stosowanie mnożeń, ale wtedy trafienia w pamięć były mniej istotne, a podziały znacznie gorsze. Obecnie oceniam czytelność wyżej, ale jeśli nie ma różnicy w czytelności, myślę, że dobrym nawykiem jest wybieranie mnożenia.

Napisz, którekolwiek z nich jaśniej określa twój zamiar.

Gdy program zacznie działać, dowiedz się, co jest powolne, i przyspiesz to.

Nie rób tego na odwrót.

Rób wszystko, czego potrzebujesz. Pomyśl najpierw o swoim czytelniku, nie martw się o wydajność, dopóki nie upewnisz się, że masz problem z wydajnością.

Kompilator wykona wydajność za Ciebie.

Jeśli pracujesz z liczbami całkowitymi lub typami nie zmiennoprzecinkowymi, nie zapomnij o operatorach przesunięcia bitów: << >>

    int y = 10;
    y = y >> 1;
    Console.WriteLine("value halved: " + y);
    y = y << 1;
    Console.WriteLine("now value doubled: " + y);

Właściwie jest dobry powód, że zgodnie z ogólną zasadą mnożenie będzie szybsze niż dzielenie. Dzielenie zmiennoprzecinkowe w sprzęcie odbywa się za pomocą algorytmów przesunięcia i warunkowego odejmowania („dzielenie długie” z liczbami binarnymi) lub - co bardziej prawdopodobne w dzisiejszych czasach - za pomocą iteracji, takich jak algorytm Goldschmidta . Przesunięcie i odjęcie wymaga co najmniej jednego cyklu na bit precyzji (iteracje są prawie niemożliwe do zrównoleglenia, podobnie jak przesunięcie i dodanie mnożenia), a algorytmy iteracyjne wykonują co najmniej jedno mnożenie na iterację. W obu przypadkach jest wysoce prawdopodobne, że podział zajmie więcej cykli. Oczywiście nie wyjaśnia to dziwactw kompilatorów, przenoszenia danych ani precyzji. Jednak ogólnie rzecz biorąc, jeśli kodujesz wewnętrzną pętlę w części programu wrażliwej na czas, pisanie 0.5 * xlub 1.0/2.0 * xraczej x / 2.0jest to rozsądne. Pedanteria „kodowania tego, co najjaśniejsze” jest absolutnie prawdziwa, ale wszystkie trzy są tak bliskie czytelności, że pedanteria jest w tym przypadku po prostu pedantyczna.

Zawsze nauczyłem się, że mnożenie jest bardziej wydajne.

Mnożenie jest zwykle szybsze - na pewno nigdy wolniejsze. Jeśli jednak nie jest to krytyczne dla szybkości, napisz, co jest najwyraźniejsze.

Dzielenie zmiennoprzecinkowe jest (ogólnie) szczególnie powolne, więc chociaż mnożenie zmiennoprzecinkowe jest również stosunkowo wolne, prawdopodobnie jest szybsze niż dzielenie zmiennoprzecinkowe.

Ale jestem bardziej skłonny odpowiedzieć „to naprawdę nie ma znaczenia”, chyba że profilowanie wykazało, że dzielenie jest wąskim gardłem w porównaniu z mnożeniem. Domyślam się jednak, że wybór mnożenia lub dzielenia nie będzie miał dużego wpływu na wydajność w Twojej aplikacji.

To staje się bardziej pytaniem, kiedy programujesz w asemblerze lub być może C. Wydaje mi się, że w większości współczesnych języków taka optymalizacja jest wykonywana za mnie.

Uważaj na to, że „zgadywanie, że mnożenie jest zazwyczaj lepsze, więc staram się tego trzymać podczas kodu”.

W kontekście tego konkretnego pytania, lepsze tutaj oznacza „szybciej”. Co nie jest zbyt przydatne.

Myślenie o szybkości może być poważnym błędem. Istnieją głębokie implikacje błędów w konkretnej algebraicznej formie obliczeń.

Zobacz Arytmetyka zmiennoprzecinkowa z analizą błędów . Zobacz Podstawowe zagadnienia arytmetyki zmiennoprzecinkowej i analizy błędów .

Chociaż niektóre wartości zmiennoprzecinkowe są dokładne, większość wartości zmiennoprzecinkowych jest przybliżeniem; są jakaś idealna wartość plus jakiś błąd. Każda operacja dotyczy idealnej wartości i wartości błędu.

Największe problemy wynikają z próby manipulowania dwiema prawie równymi liczbami. W wynikach dominują bity znajdujące się najbardziej po prawej stronie (bity błędu).

>>> for i in range(7):
...     a=1/(10.0**i)
...     b=(1/10.0)**i
...     print i, a, b, a-b
... 
0 1.0 1.0 0.0
1 0.1 0.1 0.0
2 0.01 0.01 -1.73472347598e-18
3 0.001 0.001 -2.16840434497e-19
4 0.0001 0.0001 -1.35525271561e-20
5 1e-05 1e-05 -1.69406589451e-21
6 1e-06 1e-06 -4.23516473627e-22

W tym przykładzie widać, że gdy wartości stają się mniejsze, różnica między prawie równymi liczbami tworzy niezerowe wyniki, w których prawidłowa odpowiedź to zero.

Czytałem gdzieś, że mnożenie jest bardziej wydajne w C / C ++; Brak pomysłu na języki tłumaczone - różnica jest prawdopodobnie nieistotna ze względu na wszystkie inne koszty ogólne.

O ile nie stanie się to problemem, trzymaj się tego, co jest łatwiejsze w utrzymaniu / czytelności - nienawidzę, gdy ludzie mi to mówią, ale to takie prawdziwe.

Sugerowałbym generalnie mnożenie, ponieważ nie musisz spędzać cykli, upewniając się, że twój dzielnik jest różny od 0. Oczywiście nie ma to zastosowania, jeśli twój dzielnik jest stałą.

Java android, wyprofilowana na Samsung GT-S5830

public void Mutiplication()
{
    float a = 1.0f;

    for(int i=0; i<1000000; i++)
    {
        a *= 0.5f;
    }
}
public void Division()
{
    float a = 1.0f;

    for(int i=0; i<1000000; i++)
    {
        a /= 2.0f;
    }
}

Wyniki?

Multiplications():   time/call: 1524.375 ms
Division():          time/call: 1220.003 ms

Dzielenie jest około 20% szybsze niż mnożenie (!)

Podobnie jak w przypadku postów # 24 (mnożenie jest szybsze) i # 30 - ale czasami oba są równie łatwe do zrozumienia:

1*1e-6F;

1/1e6F;

~ Uważam, że oba są równie łatwe do odczytania i muszę je powtarzać miliardy razy. Warto więc wiedzieć, że mnożenie jest zwykle szybsze.

Jest różnica, ale zależy od kompilatora. Na początku w vs2003 (c ++) nie dostałem żadnej znaczącej różnicy dla typów podwójnych (64-bitowa zmiennoprzecinkowa). Jednak przeprowadzając testy ponownie na vs2010, wykryłem ogromną różnicę, nawet czterokrotnie szybszą dla mnożenia. Śledząc to, wydaje się, że vs2003 i vs2010 generują inny kod FPU.

W przypadku Pentium 4 2,8 GHz w porównaniu z 2003:

• Mnożenie: 8,09
• Rejon: 7,97

Na Xeon W3530, vs2003:

• Mnożenie: 4,68
• Podział: 4.64

Na Xeon W3530, vs2010:

• Mnożenie: 5,33
• Rejon: 21.05.2018

Wygląda na to, że w vs2003 dzielenie w pętli (więc dzielnik był używany wielokrotnie) zostało przetłumaczone na mnożenie z odwrotnością. W vs2010 ta optymalizacja nie jest już stosowana (przypuszczam, że między tymi dwiema metodami jest nieco inny wynik). Zauważ również, że procesor wykonuje podziały szybciej, gdy tylko twój licznik wynosi 0,0. Nie znam dokładnego algorytmu wbudowanego w chip, ale może jest to zależne od liczby.

Edycja 18-03-2013: obserwacja dotycząca vs2010

Oto głupia, zabawna odpowiedź:

x / 2,0 nie jest równoważne z x * 0,5

Powiedzmy, że napisałeś tę metodę 22 października 2008 r.

double half(double x) => x / 2.0;

Teraz, 10 lat później, dowiesz się, że możesz zoptymalizować ten fragment kodu. Do metody odwołują się setki formuł w całej aplikacji. Więc zmieniasz to i doświadczasz niezwykłej 5% poprawy wydajności.

double half(double x) => x * 0.5;

Czy była to słuszna decyzja o zmianie kodu? W matematyce te dwa wyrażenia są rzeczywiście równoważne. W informatyce nie zawsze się to sprawdza. Więcej informacji można znaleźć w artykule Minimalizowanie skutków problemów z dokładnością . Jeśli obliczone wartości zostaną - w pewnym momencie - porównane z innymi wartościami, zmienisz wynik przypadków skrajnych. Na przykład:

double quantize(double x)
{
    if (half(x) > threshold))
        return 1;
    else
        return -1;
}

Najważniejsze jest to; kiedy już zdecydujesz się na jedno z dwóch, trzymaj się tego!

Cóż, jeśli założymy, że operacja dodawania / podrzędnej ścieżki kosztuje 1, to pomnóż koszty 5 i podziel koszty około 20.

Po tak długiej i interesującej dyskusji oto moje zdanie: Nie ma ostatecznej odpowiedzi na to pytanie. Jak niektórzy zauważyli, zależy to zarówno od sprzętu (por. Piotrk i gast128 ), jak i kompilatora (por. Testy @Javier ). Jeśli szybkość nie jest krytyczna, jeśli Twoja aplikacja nie musi przetwarzać w czasie rzeczywistym ogromnych ilości danych, możesz zdecydować się na przejrzystość za pomocą dzielenia, podczas gdy jeśli problemem jest szybkość przetwarzania lub obciążenie procesora, najbezpieczniejsze może być mnożenie. Wreszcie, jeśli nie wiesz dokładnie, na jakiej platformie zostanie wdrożona Twoja aplikacja, benchmark nie ma znaczenia. A dla przejrzystości kodu wystarczy jeden komentarz!

Technicznie nie ma czegoś takiego jak dzielenie, jest po prostu mnożenie przez elementy odwrotne. Na przykład nigdy nie dzielisz przez 2, w rzeczywistości mnożysz przez 0,5.

„Dzielenie” - oszukujmy się, że istnieje przez chwilę - jest zawsze trudniejsze niż mnożenie, ponieważ aby „podzielić” xprzez yjeden, trzeba najpierw obliczyć taką wartość y^{-1}, y*y^{-1} = 1a następnie wykonać mnożenie x*y^{-1}. Jeśli już wiesz, y^{-1}to nie obliczanie tego z ymusi być optymalizacją.