¿Cómo encuentran las computadoras el módulo?

Question

¿Hay algún algoritmo genial con operaciones de bits?

Answer 1

A menudo, las operaciones de módulo y dividir en un procesador son la misma cosa. Por ejemplo, consulte http://jsimlo.sk/docs/cpu/index.php/div.html. Esta es la implementación de la instrucción dividir en procesadores Intel.

Answer 2

La mayoría de las veces, el módulo se calcula dividiendo los dos números. El cociente se almacena en un registro, y el resto se almacena en el otro registro. Usted iría después del resto.

Answer 3

x mod y = x - y * (x/y)

donde (x/y) es una división entera.

Answer 4

Aparte del método obvio usando DIV y IDIV (para x86) como se mencionó anteriormente, el resultado de cualquier número modulo'd por una potencia de dos se puede calcular tomando el bit a bit y: x mod y donde y es pow2 es el igual que x AND (y - 1). La mayoría de los compiladores realizan esto cuando es posible, ya que la división es mucho más costosa que operaciones bit a bit

Answer 5

Si el divisor es conocido de antemano (por ejemplo, para código producido por un compilador C, esta es una constante conocida en tiempo de compilación) a partir del cual el módulo se puede obtener fácilmente) a veces se puede implementar con una multiplicación y un cambio. Consulte this article para obtener más información (advertencia: esto no es una lectura ligera).

En muchos procesadores, la multiplicación de enteros es mucho más rápida que la división de enteros; algunos procesadores ni siquiera tienen un código de operación de división entera (multiplicación en n -los valores de bits se pueden optimizar en un circuito de profundidad O (log n), mientras que no existe un método conocido para optimizar un circuito de división por debajo de una profundidad de O (n)).