Nie pytam o to, jak działa matematyczne pojęcie modułu ani jak 20 % 3 == 2 Dobrze to rozumiem. Jestem bardziej ciekawy, w jaki sposób kompilator / interpreter to określa. Przychodzi mi na myśl bardzo sposób na zrobienie tego, na przykład:
int modulus(int a, int b) { while (a > b) { a -= b; } return a; } (oczywiście wymaga to kilku dodatkowych przypadków, ponieważ a może być mniejsze niż b, ale masz pomysł.) Ale spowodowałoby to poważne problemy z wydajnością. Dodałem razem trochę C ++, aby przetestować wydajność obu modułów operator i moja naiwna funkcja.
#include <iostream> #include <chrono> #include <limits> #include "chrono_io" using namespace std; typedef chrono::high_resolution_clock Clock; int mod(int a, int b) { while (a > b) { a -= b; } return a; } int main() { auto start = Clock::now(); cout << 20 % 3 << endl; auto end = Clock::now(); cout << "Modulus on a small number took " << end - start << " seconds to calculate.\n"; start = Clock::now(); cout << numeric_limits<int>::max() % 3 << endl; end = Clock::now(); cout << "Modulus on a large number took " << end - start << " seconds to calculate.\n"; start = Clock::now(); cout << mod(20, 3) << endl; end = Clock::now(); cout << "My modulus function on a small number took " << end - start << " seconds to calculate.\n"; start = Clock::now(); cout << mod(numeric_limits<int>::max(), 3) << endl; end = Clock::now(); cout << "My modulus function on a large number took " << end - start << " seconds to calculate.\n"; } a wynik to:
2 Modulus on a small number took 43629 nanoseconds seconds to calculate. 1 Modulus on a large number took 5644 nanoseconds seconds to calculate. 2 My modulus function on a small number took 3682 nanoseconds seconds to calculate. 1 My modulus function on a large number took 2153824554 nanoseconds seconds to calculate. operator modułu wahał się od 4 000 do 70 000 nanosekund. Moja funkcja zawsze wygrywała na małych liczbach, ale zajęła około 2 sekundy na dużej liczbie. Ponieważ operator modułu jest o wiele bardziej spójny, zakładam, że porównuje liczbę na poziomie bitowym.
Jak więc działa operator modułu? Mogę wymyślić kilka przypadków, które byłyby bardzo łatwe do określenia. Na przykład w przypadku mod 2 można po prostu spojrzeć na bardzo ostatni bajt.Lub za pomocą mod 4 możesz spojrzeć na przedostatnią b yte. Ale nie wszystkie liczby mają taki prosty wzór.
Komentarze
Odpowiedź
Prawie wszystkie procesory mają jedną instrukcję, która zwraca moduł wartości. Weźmy na przykład pod uwagę ten program:
int main() { int i = 10; return i % 3; } Jeśli skompiluję go na moim komputerze z systemem Intel OS X przy użyciu g ++ -S, w rezultacie otrzymam szablon i to:
movl $3, %eax movl $0, -4(%rbp) movl $10, -8(%rbp) movl -8(%rbp), %ecx movl %eax, -12(%rbp) ## 4-byte Spill movl %ecx, %eax cltd movl -12(%rbp), %ecx ## 4-byte Reload idivl %ecx movl %edx, %eax Rzeczywisty moduł uzyskuje się zgodnie z tą instrukcją: idivl %ecx. Gdy ta instrukcja zostanie wykonana, iloraz zostanie umieszczony w %eax, a reszta w %edx.
Ponieważ tak naprawdę oznacza to, że operacja % zajmie tylko kilka cykli zegara, z których większość przenosi dane do właściwego rejestru. Zauważ też, że przynajmniej w przypadku Intela ta sama operacja pozwala znaleźć zarówno iloraz, jak i resztę, więc w odniesieniu do Twojego komentarza / i % biorę dokładnie ten sam czas. To ta sama operacja. Zmienia się tylko to, z jakiego rejestru kompilator pobiera wyniki.
W przypadku dowolnego procesora wykonanego w ciągu ostatnich kilku dekad można założyć, że każda podstawowa operacja matematyczna (w tym rzeczy wyglądające jak funkcje biblioteczne, takie jak sqrt lub cos) jest w rzeczywistości pojedynczą instrukcją maszynową i zwykle zajmuje najwyżej kilka cykli zegara.
[AKTUALIZACJA]
Jak ludzie zauważyli w komentarzach, aby zobaczyć, że coś zbliża się w odpowiednim momencie, musisz usunąć dane wyjściowe z sekcji czasowej w ten sposób:
int i; auto start = Clock::now(); i = 20 % 3; auto end = Clock::now(); cout << i << endl; Ale nawet to prawdopodobnie nie jest dokładne, ponieważ rzeczywista szczegółowość czasów może przekraczać to, co jesteś próbując czasu. Zamiast tego możesz to zrobić:
int i=0; int x; auto start = Clock::now(); for(i=0;i<1000000;i++) x = i % 3; auto end = Clock::now(); cout << i << endl; Następnie podziel swój czas przez 1 000 000. (Będzie to trochę za dużo, ponieważ obejmuje czas potrzebny na zadanie, porównanie i przyrost). Na moim komputerze daje to czas 5 nanosekund.
Komentarze
- Naprawdę? Powiedziano mi, że sqrt to bardzo powolna instrukcja.
- Zobacz stackoverflow.com / questions / 7724061 / …
- @StevenBurnap ta odpowiedź jest nieco nieaktualna, oparta na architekturze z 2011 roku. Według Agner Fog ' tabela, która jest aktualizowana co najmniej raz w roku , instrukcje Haswell SSE2 SQRTSS / SQRTPS (32-bitowa liczba zmiennoprzecinkowa, z 23 bitami istotności) ma opóźnienie 11 cykli, SQRTSD / SQRTPD (64-bitowa liczba zmiennoprzecinkowa) ma opóźnienie 16 cykli. Instrukcje te są dokładne, tj. Nie należą do wariantów szybkiego przybliżenia. Rzeczywiście, jest dużo wolniej w starszych architekturach. Pamiętaj też, że wywołanie
std::sqrt()powoduje wywołanie biblioteki w większości kompilatorów C ++. - Kompilatory mogą dodatkowo zastosować optymalizację redukcji siły w szczególnych przypadkach. Na przykład x% 2 może zostać zoptymalizowany do maski bitowej, jeśli ' jest szybsze na określonej architekturze.
- @rwong Pomyślałbym, że
std:sqrtbyłby zwykle wbudowany (i używa zestawu wbudowanego). Ale ja ' nigdy nie sprawdzałem.
DIViIDIV, które wykonują dzielenie liczb całkowitych, również przechowują resztę w rejestrze). Zastanawiasz się, jak działa sprzęt ?cout <<większości operacji. Wątpię, czy rzeczywiście mógłbyś zmierzyć czas potrzebny procesorowi na wykonanie20 % 3, nawet jeśli kompilator nie ' i tak nie zrobił tego w czasie kompilacji .