CPU est plus d'opération MOD intensive que la multiplication?

StackOverflow https://stackoverflow.com/questions/4109330

  •  29-09-2019
  •  | 
  •  

Question

Pourquoi le fonctionnement de MOD plus cher que multiplication par un peu plus d'un factor of 2? S'il vous plaît être plus précis sur la façon dont le fonctionnement de la division CPU PerForm et renvoie le résultat pour le fonctionnement MOD.

Dans l'exemple suivant les fils de chaque exécution d'une seconde. Le test a été effectué sur un processeur 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.
}
Était-ce utile?

La solution

Les algorithmes (processeurs exécutent la division et la multiplication par des algorithmes mis en œuvre dans les portes) pour la division sont plus coûteuses que pour la multiplication. En fait, certains algorithmes de division qui ont une bonne complexité utilisent la multiplication comme une étape de base.

Même si vous utilisez les algorithmes naïfs qui sont apprises à l'école. Ils ont tous deux la même complexité asymptotique, mais la constante de la division est plus grande (vous devez trouver le chiffre et qui n'est pas trivial, donc vous pouvez gâcher et doivent réparer le gâchis).

Autres conseils

MOD est une opération de division, pas une opération de multiplication. La division est plus cher que la multiplication.

Plus d'informations sur le fonctionnement ici MOD: http://en.wikipedia.org/wiki/Modulo_operation

Instruction latences et débit pour les processeurs AMD et Intel x86

Une opération est juste en soi plus lent à la CPU:)

Oui, mod est plus cher que la multiplication, car il est mis en œuvre par la division. (CPU retourne généralement à la fois quotient et reste de la division.) Mais utiliser vos deux fils multiplication. copier / coller erreur?

mod est essentiellement le même processus que la division (certains systèmes fournissent une « divmod » pour cette raison).

La grande différence entre mulitplication binaire longue et longue division binaire est cette longue division vous oblige à effectuer un test de débordement après chaque soustraction, tandis que de longues effectue de mutiplication l'addition sans condition après le processus de masquage initial.

Cela signifie que vous pouvez easilly réorganiser et paralleise les addditions dans la multiplication longue, mais vous ne pouvez pas faire la même chose pour la division longue. J'ai écrit une réponse plus à ce sujet à https://stackoverflow.com/a/53346554/5083516

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top