Nežádám, abych se ptal, jak funguje matematický koncept modulu, nebo jak 20 % 3 == 2 tomu rozumím. Jsem zvědavější, jak to určuje překladač / tlumočník. Napadá mě velmi naivní způsob, jak to udělat, například:
int modulus(int a, int b) { while (a > b) { a -= b; } return a; } (Je zřejmé, že to vyžaduje několik dalších případů, protože a může být menší než b, ale máte představu.) Ale to by mělo nějaké vážné problémy s výkonem. Hodil jsem dohromady C ++, abych otestoval účinnost obou modulů operátor a moje naivní funkce.
#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 výstup je:
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. The operátor modulu se pohyboval od 4 000 do 70 000 nanosekund. Moje funkce vždy zvítězila u malých čísel, ale u velkého počtu to trvalo asi 2 sekundy. Protože operátor modulu je mnohem konzistentnější, předpokládám, že porovnává číslo na bitové úrovni.
Jak tedy funguje operátor modulu? Napadají mě některé případy, které by bylo velmi snadné určit. Například u modu 2 se stačí podívat na velmi poslední bajt. Nebo s modem 4 se můžete podívat na předposlední b yte. Ale ne všechna čísla mají tak jednoduchý vzor.
Komentáře
Odpověď
Téměř všechny CPU mají jedinou instrukci, která vrátí modul hodnoty. Zvažte například tento program:
int main() { int i = 10; return i % 3; } Pokud to zkompiluji na svém stroji Intel OS X pomocí g ++ -S, výsledkem bude nějaký typický štítek a toto:
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 Skutečný modul se stane s touto instrukcí: idivl %ecx. Po provedení této instrukce bude kvocient umístěn do %eax a zbytek do %edx.
Vzhledem k tomu, že to ve skutečnosti znamená, že operace % bude trvat jen několik hodinových cyklů, z nichž většina ve skutečnosti přesouvá data do správného registru. Všimněte si také, že přinejmenším u Intel najde stejná operace kvocient i zbytek, takže s odkazem na váš komentář / a % trvat přesně stejnou dobu. Je to stejná operace. Jediná věc, která se mění, je to, z jakého registru získá kompilátor výsledky.
U všech procesorů provedených v posledních několika desetiletích můžete předpokládat, že každá základní matematická operace (včetně věcí, které vypadají jako funkce knihovny jako sqrt nebo cos) je ve skutečnosti jediná strojová instrukce a obvykle trvá maximálně několik hodinových cyklů.
[UPDATE]
Jak již lidé uvedli v komentářích, abyste viděli, jak se něco blíží správnému načasování, je třeba odebrat výstup z časované sekce takto:
int i; auto start = Clock::now(); i = 20 % 3; auto end = Clock::now(); cout << i << endl; Ale ani to pravděpodobně není přesné, protože skutečná zrnitost časování může překročit to, čím jste snaží se načasovat. Místo toho možná budete chtít udělat toto:
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; Poté vydělte své načasování o 1 000 000. (To bude o něco vyšší, protože zahrnuje čas potřebný pro přiřazení, srovnání a přírůstek.) Na mém počítači to dává čas 5 nanosekund.
Komentáře
- Opravdu? Bylo mi řečeno, že sqrt je velmi pomalá instrukce.
- Viz stackoverflow.com / questions / 7724061 / …
- @StevenBurnap je tato odpověď na základě architektury v roce 2011 trochu zastaralá. Podle tabulka Agner Fog ‚ s aktualizací alespoň jednou ročně , pokyny Haswell SSE2 SQRTSS / SQRTPS (32bitový float, s 23 bity významnosti) má latenci 11 cyklů, SQRTSD / SQRTPD (64bitový float) má latenci 16 cyklů. Tyto pokyny jsou přesné, tj. Nikoli z variant rychlé aproximace. Ve starších architekturách je to opravdu mnohem pomalejší. Nezapomeňte také, že volání
std::sqrt()vyvolá volání knihovny ve většině překladačů C ++. - Překladače mohou ve zvláštních případech navíc použít optimalizaci snížení pevnosti. Například x% 2 může být optimalizováno na bitovou masku, pokud je ‚ rychlejší na konkrétní architektuře.
- @rwong Myslel bych si, že
std:sqrtby obvykle byly vložené (a používaly vložené sestavení.) Ale ‚ jsem to nikdy nekontroloval.
IDIV, které provádějí celočíselné dělení, také zbytek uloží do registru). Ptáte se, jak to hardware dělá?cout <<většinu operací. Pochybuji, že byste mohli skutečně změřit čas, který procesor potřebuje20 % 3, i když kompilátor to ‚ stejně neudělal .