6.9. División y Módulo.

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úmero x entre un número y teniendo como cociente r y como residuo m. Para dividir lo que hacemos es ir multiplicando por dos al divisor y mientras que no sea mayor que el dividendo x. 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 en p. De esta forma obtenemos que:
x = 2p×y + s
Donde s es el sobrante de x con respecto a 2p×y. Tomamos a s y 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, sk se convierte en m). Factorizando y obtenemos:
x = (2p0 + 2p1 + … + 2pky + sk
y sabemos que:
x = r×y + m
Por lo tanto, el resultado de la división r lo 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).


Problema ejemplo


Si Fuéramos Niños Otra Vez

“¡Ooooooooooooooo!
¡Si las matemáticas fueran tan sencillas como las de la primaria!
¡Estoy seguro que nunca volvería a equivocarme!”
Comenta un estudiante universitario inteligente.
Pero su maestra que es todavía más inteligente le responde - “¡Está bien! Eso mismo es lo que vamos a hacer para el proyecto de programación. Así que no sigas lamentándote.”
“¡En serio!” - dice el estudiante. Y está tan contento que no nota la sonrisa de la maestra.

Problema
El primer proyecto de este pobre estudiante es crear una calculadora que pueda realizar las operaciones aritméticas básicas.

Pero, como muchos otros estudiantes, no le gusta trabajar en los proyectos. Prefiere sólo juntar programas que va encontrando. Siendo amigo tuyo, te pide que le hagas el proyecto. Pero como ya lo conoces bien, decides ayudarlo sólo con la división y módulo (% en C/C++) de números enteros.

Entrada
La entrada contiene una serie de líneas. Cada línea tendrá un número, uno o varios espacios, un signo (de división o módulo), más espacios, y otro número. Ambos números son enteros no negativos. El primero puede ser arbitrariamente grande, mientras que el segundo número n estará en el rango (0 < n < 231).

Salida
Una línea que contenga un entero por cada operación en la entrada. La salida no debe tener espacios adicionales.

Solución: Al igual que con el problema anterior, sólo debemos implementar los algoritmos para hacer las operaciones que nos piden. Por el tamaño n, podríamos implementar una división de un número grande entre un longint. No lo vamos a hacer así por fines didácticos.


Código



Las primeras 10 líneas son casi las mismas que en el problema anterior. Definimos el tamaño de los bloques, el número máximo de bloques, el modulo a utilizar y la estructura de los números grandes. La única diferencia es el número máximo de bloques a utilizar.

En este caso, en ninguna parte del problema mencionan el tamaño máximo del número y se limitan a decir que pueden ser arbitrariamente grandes. Tenemos varias alternativas a seguir dependiendo de la situación en la que nos encontremos. Una opción es crear una implementación dinámica de número grandes. Otras alternativas son: si nos encontramos en un concurso, podemos preguntar el tamaño a los jueces; dentro de un concurso en línea, podemos sobredimensionar tanto como nos lo permita la memoria disponible; y si estamos entrenando, podemos hacerlo a prueba y error, o entrar a los foros y esperar que alguien ya halla obtenido un acotamiento.

Las siguientes cuatro líneas de código (líneas 12 a 15) son donde declaramos las variables a utilizar. En el caracter ch vamos a guardar la operación a realizar, dentro de n guardamos el segundo número (el divisor), y las variables x e y nos sirven para realizar las operaciones con los números grandes.

Las funciones y procedimientos inicia_cero (línea 17), inicia_numero (línea 19), menor_igual (línea 21), shift_r (línea 23), shift_l (línea 25), resta (línea 27) e imprime (línea 102) son los mismos que se emplearon en el problema anterior y que implementamos en secciones anteriores.

La funciones divide (líneas 29 a 51) y modulo (líneas 53 a 75) son el mismo código excepto que devuelven resultados distintos. Tomando como referencia divide, en las líneas 33 a 38 vamos desplazando el divisor hasta que se vuelve más grande que el dividendo. La cantidad de desplazamientos que realizamos lo guardamos en p. En la línea 39 iniciamos el resultado de la división a cero. Después, por cada corrimiento a la izquierda que hicimos, vamos a efectuar uno a la derecha. Si el divisor es menor o igual al dividendo, se lo restamos e incrementamos en 1 el resultado. El resultado lo desplazamos un lugar a la izquierda en cada ciclo.

Esperaríamos que si el divisor es menor o igual, el resultado lo deberíamos incrementar en 2i. Para evitar hacer esto lo incrementamos en 1 y lo desplazamos en cada ciclo. Veamos porque funciona: al incrementar en 2i equivale a agregar un 1 en la posición i del número en binario. Esto lo cambiamos por incrementar la posición 0, y al recorrer el número i veces queda en su posición esperada.

En el procedimiento lee (líneas 77 a 100) tenemos una ligera variación: en lugar de leer el número en una sola línea, tenemos que leerlo hasta encontrar un espacio. Para hacer esto, cambiamos el readln por las instrucciones que se encuentran de la línea 84 a 89. Esto es, auxiliarnos de una variable temporal ch para leer los caracteres y anexarlos de uno en uno a la cadena.

Terminamos con la parte principal del código (líneas 104 a 117), donde leemos los números y la operación a evaluar, y la realizamos. Hacemos esto mientras no lleguemos al fin de archivo.


Casos ejemplo

Entrada: 417 / 29
Desarrollo:  y     x
29  ≤ 417, p= 0
58  ≤ 417, p= 1
116 ≤ 417, p= 2
232 ≤ 417, p= 3
464 > 417

232 ≤ 417, r= 1
116 ≤ 185, r= 3
58  ≤  69, r= 7
29  >  11, r= 14
       11
Salida: 14

Entrada: 253 % 13
Desarrollo:  y     x
13  ≤ 253, p= 0
26  ≤ 253, p= 1
52  ≤ 253, p= 2
104 ≤ 253, p= 3
208 ≤ 253, p= 4
416 > 253

208 ≤ 253, r= 1
104 >  45, r= 2
52  >  45, r= 4
26  ≤  45, r= 9
13  ≤  19, r= 19
        6
Salida: 6


Código en C



Tiempo de ejecución

Lenguaje Fecha Tiempos [s] Memoria [Kb]
Ejecución Mejor Mediana Peor
Pascal 16-Feb-2006 0.031 0.000 0.004 3.469 Minimum
C 16-Feb-2006 0.029 Minimum





© Pier Paolo Guillen Hernandez
World of πer