martes, 1 de mayo de 2012

Exponenciacion binaria y modular

Hola, estuve haciendo un par de cosas y tuve que usar un algoritmo de exponenciacion binaria y modular pero no queria que fuera recursivo asi que luego de algunos intentos, esto fue lo que consegui, espero les pueda servir de ayuda, tanto como a mi(aunque esta en java se entiende si manejas otro lenguaje :P) :

public static int expomod(int a, long b,int mod){
    int res = 1;
    while(b>0){
        if((b&1)==1)
            res=(a*res)%mod;
    b>>=1;
    a=((a%mod)*(a%mod))%mod;
    }
return res;
}

y el algoritmo en python es:
def ex(a, b,m):
     r = 1
     while(b):
             if(b&1):
                     r = (r*a)%m
             b>>=1
             a = ((a%m)*(a%m))%m
     return r

La verdad luego de ver el algoritmo recursivo, se entiende este. Lo que se hace es cambiar la recursividad a las variables, por decirlo de alguna forma. Saludos y espero sus comentarios!

Un buen tutorial donde se tratan a fondo otros algoritmos relacionados es este de topcoder.

Nota: un problema en donde se puede aplicar este algoritmo es este.