Ridicare la putere in timp logaritmic. O(log N)

fast_pow.java

/*
2^10
pow(2,10)

2 * 2 * 2 * ....* 2
de 10 ori

fast_pow(2,10) 

log n = log 10 = logaritm in baza 2 din 10 = 3 

numarul de pasi pentru a calcula pow(2, 10) = 3


n = 10000

4^100

10 in baza 2 = 1010

       a * a^n-1  
a^n = 

       a * a^(n/2) 


       n = 2
       exp = 3

       101 
       001
       ===
       001


       n = 2
       exp = 3
       pow(n,exp) = 2^3 = 8

       exp = 3 = 011 >>1 => 001 >> 000

*/
public class Main {

    //complexitate O(n) - liniara
	static int pow(int a, int n) {

		int p = 1;

		for(int i = 1; i <= n; ++i) p *= a;

		return p;
	}

	//Complexitate O(log n) - ridicare la putere in timp logaritmic
                        //2          3
	static long fast_pow(long base, int exp) {

           long result = 1;

           while(exp > 0) {//3//1>0

           	   if((exp & 1 )== 1) result = result * base; //daca exponentul este impar// result = 1 * 2 = 2 =>2*4=8

           	   base = base * base;//2*2 = 4

           	   exp >>= 1;//011>>1=001 (3/2) = 1 . 1/2 001>>1 = 0
           	   //exp = exp / 2;
           } 

           return result;

	}

    //implementarea log in baza 2 din a
	static int log2Fast(int a) {


		   int cnt = 0;

		   while((a >>= 1) != 0) { //10 >> 1 = 5 >> 1 = 2 >> 1 >> 1 = 0

		   	  cnt++;
		   }

		   return cnt;
	}


    public static void main(String[] args) {

           int n = 10;

           System.out.println(pow(2,20));//2*2*....*20 
           System.out.println(fast_pow(2,20));//log 20 pasi
           System.out.println(log2Fast(20));
           System.out.println(log2Fast(10));//logaritm in baza 2 din 10
           System.out.println(log2Fast(8)); 

           // n -> infinit size este foarte MARE

           //pow(2,10) 10 in baza 2 = 1010 => 0101 = 5 >> 1 => 0010 >> 1 = 0001 >> 1 >0000

    } 
}