Existe un modulo para la division en los numeros naturales y porque?

El módulo es el residuo de la división, por lo que el algoritmo es el mismo en ambos casos y solamente cambia el valor que devuelve la función.

Igual que con la multiplicación, utilizamos un método en base dos descubierto por los antiguos egipcios.

Antes de empezar a analizar el método, recordemos el nombre de los operandos y los resultantes en la división :

Supongamos que queremos dividir un númeroxentre un númeroyteniendo como cocientery como residuom.

Para dividir lo que hacemos es ir multiplicando por dos al divisorymientras que no sea mayor que el dividendox.

Nos acordamos del tema anterior que multiplicar por dos es equivalente a un desplazamiento a la izquierda, y que este último es mucho más rápido.

Guardamos la cantidad de multiplicaciones que efectuamos enp.

De esta forma obtenemos que :

x = 2p×y + s

Dondeses el sobrante dexcon respecto a 2p×y.

Tomamos asy repetimos todo el proceso.

Esto lo seguimos efectuando hasta que el sobrante que tengamos sea menor que el divisor.

Al final tendremos algo de la forma :

x = 2p0×y + 2p1×y + … + 2pk×y + sk

Como el sobrante es menor el divisor, es equivalente el residuo (esto es, skse convierte enm).

Factorizandoyobtenemos :

x = (2p0 + 2p1 + … + 2pk)×y + sk

y sabemos que :

x = r×y + m

Por lo tanto, el resultado de la divisiónrlo podemos obtener sumando todas las potencias de dos que utilizamos.

De manera similar a la multiplicación, el tiempo de ejecución es O(n2) y existen mejores algoritmos.

Uno de los más utilizados se basa en técnicas “divide y vencerás” pero requiere una muy buena implementación de la multiplicación (óptimamente, la efectuada con la Transformada Rápida de Fourier).