package br.org.agilcoop.cursos.testes.unidade;

 public class MathHelper {

         public static long mdcAlgoritmoSuperLento(long a, long b) {

                 long maior = Math.max(a, b);

                 long menor = Math.min(a, b);

                 if(maior < 0 || menor < 0) throw new IllegalArgumentException("must be positive");

                 if(maior == 0  || menor == 0) return 0;

                 // 10 e 5 = 5

                 long mdc = 1;

                 for(long i = 2; i <= menor; i++) {

                         if(maior % i == 0 && menor % i == 0)

                                 mdc = i;

                 }

                 return mdc;

         }

         // Algoritmo de Euclides: mdc(a, b) = mdc(b, r) onde r: a = q * b + r

         public static long mdcAlgoritmoEuclides(long a, long b) {

                 long valor = Math.max(a, b);

                 long divisor = Math.min(a, b);

                 if(valor < 0 || divisor < 0) throw new IllegalArgumentException("must be positive");

                 if(valor == 0  || divisor == 0) return 0;

                 long resto = valor % divisor;                

                 while(resto != 0) {

                         valor = divisor;

                         divisor = resto;

                         resto = valor % divisor;

                 }

                 return divisor;

         }

         //        Dois números naturais sempre têm divisores comuns.

         public static long mdc(long a, long b) {

                 return mdcAlgoritmoEuclides(a, b);

         }

         // calcula (num^exp) mod n

         //http://en.wikipedia.org/wiki/Modular exponentiation

         public static long potenciaModulo(long num, long exp, long n) {

                 long result = 1;                

                 while (exp > 0) {

                         if ((exp & 1) > 0) result = (result * num) % n;

                         exp >>= 1;

                         num = (num * num) % n;

                 }                

                 return result;

         }

 }