È operazione MOD più impegnativo per la CPU di moltiplicazione?

Question

Perché è un'operazione MOD più costoso di multiplication da un po 'di più di un factor of 2? Si prega di essere più specifico su come operazione di divisione esegue CPU e restituisce il risultato per il funzionamento MOD.

Nel seguente esempio i fili ogni corsa per un secondo. Il test è stato eseguito su un processore SPARC.

// multiplication
void someThread() {

    int a = 10234;
    while (true) {
        opers++;
        a = a * a;
        a++;
    }

    // opers ~ 26 * 10^6 in a sec.
}

// MOD
void someThread() {

    int a = 10234;
    while (true) {
        opers++;
        a = a % 10000007;
        a++;
    }

    // opers ~ 12 * 10^6 in a sec.
}

Answer 1

Algoritmi (processori eseguono la divisione e la moltiplicazione per algoritmi implementati in gate) per la divisione sono più costosi rispetto per la moltiplicazione. È un dato di fatto, alcuni algoritmi per divisione che hanno una buona complessità utilizzano la moltiplicazione come un passo fondamentale.

Anche se si utilizzano gli algoritmi ingenui che vengono apprese a scuola. Entrambi hanno la stessa complessità asintotica, ma la costante per la divisione è maggiore (si deve scoprire la cifra e che non è banale, in modo da poter rovinare e devono risolvere il pasticcio).

Answer 2

MOD è un'operazione di divisione, non un'operazione di moltiplicazione. Divisione è più costoso di moltiplicazione.

Maggiori informazioni sul funzionamento MOD qui: http://en.wikipedia.org/wiki/Modulo_operation

Answer 3

latenze di istruzione e il throughput per AMD e Intel x86 processori

Un'operazione è solo intrinsecamente più lenta alla CPU:)

Answer 4

Sì, mod è più costoso di moltiplicazione, come viene attuata attraverso la divisione. (CPU generalmente ritorno sia quoziente e resto sulla divisione.), Ma entrambe le filettature utilizzare moltiplicazione. copia / incolla errore?

Answer 5

mod è essenzialmente lo stesso processo di divisione (alcuni sistemi prevedono la "divmod" per questo motivo).

La grande differenza tra lungo mulitplication binario e divisione lunga binaria è che a lungo divisione richiede di eseguire un test di overflow dopo ogni sottrazione, mentre lunghe esegue mutiplication l'aggiunta incondizionatamente dopo il processo di mascheratura iniziale.

Questo significa che potete easilly riorganizzare e paralleise le addditions a lungo la moltiplicazione, ma non si può fare lo stesso per lungo divisione. Ho scritto una risposta più su questo a https://stackoverflow.com/a/53346554/5083516