Come funziona il modulo?

Non sto chiedendo come funziona il concetto matematico di modulo o come 20 % 3 == 2 lo capisco bene. Sono più curioso di sapere come il compilatore / interprete determina questo. Posso pensare a un modo molto ingenuo per farlo, in questo modo:

int modulus(int a, int b) { while (a > b) { a -= b; } return a; } 

(ovviamente questo richiede qualche caso in più perché a può essere più piccolo di b, ma hai unidea.) Ma questo avrebbe alcuni seri problemi di prestazioni. Ho messo insieme un po di C ++ per testare lefficienza di entrambi i moduli operatore e la mia funzione ingenua.

#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"; } 

e loutput è:

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. 

Il Loperatore modulo variava da 4.000-70.000 nanosecondi. La mia funzione vinceva sempre sui numeri piccoli, ma impiegava circa 2 secondi sui numeri grandi. Poiché loperatore modulo è molto più coerente, presumo che confronti il numero a livello bit per bit.

Allora, come funziona loperatore modulo? Posso pensare ad alcuni casi che sarebbero molto facili da determinare. Ad esempio, con la mod 2, puoi semplicemente guardare ultimo byte oppure con il mod 4 si può guardare dal penultimo b yte. Ma non tutti i numeri hanno uno schema così semplice.

Commenti

• Sui PC, questo viene generalmente fatto in hardware (il x86 DIV e IDIV, che eseguono la divisione di numeri interi, memorizzano anche il resto in un registro). Stai chiedendo come funziona l hardware ?
• Letture correlate: Assembly Language – How to Do Modulo?
• La divisione lunga funziona allo stesso modo con i numeri binari come con i decimali. Provalo, quindi pensa a come potresti codificarlo (suggerimento: ‘ utilizzerai molti turni).
• @DJMcMayhem: Sì. A volte il compilatore deve eseguire alcune modifiche ai risultati per essere conforme alle specifiche del linguaggio per laritmetica con segno. In generale, la velocità di divisione dellhardware è abbastanza buona che quando non si conoscono i valori di input in fase di compilazione, è meglio lasciare che lo faccia lhardware invece dellemulazione del software. Tuttavia, se il divisore è noto in fase di compilazione, ci sono trucchi che potrebbero essere eseguiti più velocemente. Vedi: questo e questo .
• Tieni presente che il modo in cui stai misurando le cose in realtà stai solo misurando il tempo necessario per cout << la maggior parte delle operazioni. Dubito che tu possa effettivamente misurare il tempo impiegato dal processore per eseguire 20 % 3 anche se il compilatore ‘ non lo ha fatto comunque in fase di compilazione .