¿El funcionamiento de MOD requiere más CPU que la multiplicación?

Question

¿Por qué la operación MOD es más costosa que multiplication por un poco más que factor of 2? Sea más específico sobre cómo la CPU realiza la operación de división y devuelve el resultado para la operación MOD.

En el siguiente ejemplo, los subprocesos se ejecutan cada uno durante un segundo. La prueba se realizó en un procesador 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

algoritmos (procesadores ejecutan la división y la multiplicación por los algoritmos implementados en puertas) para la división son más costosos que para la multiplicación. Como cuestión de hecho, algunos algoritmos para la división que tienen una buena complejidad están utilizando la multiplicación como un paso básico.

Incluso si usa los ingenuos algoritmos que se aprenden en la escuela. Ambos tienen la misma complejidad asintótica, pero la constante para la división es mayor (hay que descubrir el dígito y eso no es trivial, por lo que puedes cometer un error y tener que arreglar el desorden).

Answer 2

MOD es una operación de división, no una operación de multiplicación. La división es más costosa que la multiplicación.

Más información sobre la operación MOD aquí: http://en.wikipedia.org/wiki/Modulo_operation

Answer 3

Sí, mod es más caro que la multiplicación, ya que se implementa a través de la división. (Generalmente, las CPU devuelven tanto el cociente como el resto en la división). Pero ambos subprocesos usan multiplicación. ¿copiar/pegar error?

Answer 4

Instruction latencies and throughput for AMD and Intel x86 processors

Una operación es sólo inherentemente más lento en la CPU :)