Maximo Comun Divisor de Numeros Muy grandes con BIG MOD

Introduccion:

Cuando hablamos de sacar el Maximo Común divisor MCD pensamos en algoritmos como el Euclides tanto recursivo como Iterativo, por fuerza bruta haciendo restas, e incluso el algoritmo Euclides Extendido que es un adicional al euclides normal pero que nos devuelve dos números adicionales, claro todos estos sacan el MCD pero todos estos resuelven números hasta 2^32 -1 que es lo máximo almacenable en una variable.

¿Que pasaria si les digo que me saquen el MCD de un numero de 100 dígitos con otro de una cantidad almacenable en una variable? 

En programación sabemos claramente que si hablamos de variables que almacenen dicho numero es imposible almacenarlo almenos que sea en una cadena pero y luego para operar el numero necesitaríamos convertirlo a Entero, Double, Long Int incluso Long Long en C++ pero un numero de 100 dígitos no se puede almacenar en ninguno de estos tipos de variables.

¿Entonces que hacemos? ¿Como podemos operar estos numeros?

Llamemos "nBig" al numero grande y "A" al numero pequeño.

Lo que nos interesa es MCD(nBig,A).

Pero como no es posible realizar esta operación existe una solución sacarle el modulo (MOD) a "nbig" y "A", este resultado sera un numero menor que A, entonces si sacamos el MCD (A , nBig modulo A) por congruencia este resultado sera el MCD(nBig,A) ¿Como así? pues esto ya es un poco de Teoría de Números específicamente la congruencia de dos números. Pero aun hay una duda operar el  MOD(nBig,A) es aun difícil ya que igual tenemos que operar el numero nBig y como sabemos no podemos almacenarlo en una variable.

Aquí surge una solución ¡Usar el paradigma DIVIDE Y VENCERÁS!

Este paradigma dice que para poder resolver un problema debemos dividir el problema en partes mas pequeñas y así se nos hará mas fácil resolverlo.

De manera que tendremos que sacarle el modulo a una parte de nBig con a y luego unir este resultado a nBig y volver a tomar otra parte de nBig y sacarle modulo con a y así sucesivamente hasta obtener el ultimo modulo.

¿Es posible hacer esto?

Claro, si se puede hacer y te lo muestro en un ejemplo:

Algoritmo BIG MOD:

1. tmpStr: Igual a d digitos de nBig.
2. nBig: Porcion restante de nBig.
3. tmpNum: Igual a toInteger(tmpStr).
4. tmpNum: Igual a tmpNum % a.
5. tmpStr: Igual toString(tmpNum).
6. nBig: Igual a tmpStr + nBig.

EJEMPLO:

sea d= Tamaño de subcadena a tomar de nBig para este ejemplo d=10
nBig: 123456789033333333335555555555
a: 320 // Recuerden que a es un numero almacenable en una variable entera

Encontramos nBig%a //Encontramos el modulo de estos dos numeros

1. Iteracion 1: 

Extraemos los 10 primeros digitos, tmp = 1234567890 and nBig = 33333333335555555555.
sacamos el modulo
    mod = tmp % a = 210

Agregamos el resultado como prefijo de nBig

    nBig = 21033333333335555555555

2. Iteracion 2:

tmp = 2103333333 and nBig = 3335555555555
mod = tmp % a = 213
nBig = 2133335555555555

3. Iteracion 3:

tmp = 2133335555 and nBig = 555555
mod = tmp % a = 195
nBig = 195555555

4. Iteracion 4:

tmp = 195555555 and nBig = ""
mod = tmp % a = 35
La respuesta = 35.

Ahora solo nos faltaría sacarle el MCD(320,35) y obtendremos el resultado de MCD(123456789033333333335555555555 , 320). Asi que para sacarle el MCD puedes usar cualquiera de las Alternativas que mencione al inicio.

En este Caso la respuesta es MCD(nBig,a) = 5.

Es la solución al MCD(nbig,a) usando BIG MOD(ndig,a):

Implementacion en Java:

Descarga:

Puedes descargar el Proyecto Aqui.
Este ejercicio es de la pagina web UVA que es una pagina donde se publican ejercicios que fueron propuestos en la competencia ACM-ICPC. te invito a que le des un vistazo. Adicionalmente te comparto la publicación original del ejercicio. Espero te haya gustado, si fue así Compartelo que me ayudaras mucho difundiendo mi blog, Gracias ;).

Fuente: DevX