L'opération MOD est-elle plus gourmande en ressources processeur que la multiplication?

Question

Pourquoi est-MOD opération plus cher que multiplication par un peu plus d'un factor of 2? Veuillez être plus précis sur la façon dont la CPU effectue l'opération de division et renvoie le résultat pour l'opération MOD.

Dans l'exemple suivant, les unités d'exécution s'exécutent chacune 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. 
} 

Answer 1

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 étape de base.

Même si vous utilisez les algorithmes naïfs appris à l'école. Ils ont tous les deux la même complexité asymptotique, mais la constante pour la division est plus grande (vous devez trouver le chiffre et ce n'est pas trivial, alors vous pouvez vous tromper et réparer le désordre).

Answer 2

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

Plus d'informations sur l'opération MOD ici: http://en.wikipedia.org/wiki/Modulo_operation

Answer 3

Oui, mod est plus cher que la multiplication, car il est mis en œuvre par la division. (Les processeurs renvoient généralement le quotient et le reste à la division.) Mais vos deux threads utilisent la multiplication. copier/coller une erreur?

Answer 4

Instruction latencies and throughput for AMD and Intel x86 processors

Une opération est simplement plus lent par nature à la CPU :)