CareerCup

a basic O(log(b)) solution, assuming the result shall fit in a long long. Otherwise we have to implement a method for string multiplication.

#include <iostream>

using namespace std;

computeApowB(long long a, long long b) {
	long long ret = 1;
	while(b) {
		if (b & 1) {
			ret *= a;
		}		
		a = a * a;
		b /= 2;
	}
}

This can be done in o(log b) time

divide the prob into a^b/2 * a^b/2
and further divide a^b/2 into a^b/4*a^b/4 and so


it forms a recurrence tree

int apowerb::power(int x, int y)
{
    if(y==1)
        return x;
    if(y%2==0)
        return power(x,y/2)*power(x,y/2);
    else
        return power(x,(y-1)/2)*power(x,(y-1)/2)*x;
}

int powab(int a, int b)
{
	static int val = 0;
	if (b == 1)
	{
		return a;
	}
	else
	{
		val = powab(a, b / 2);
		if (b % 2 == 0)
			return  val * val;
		else
			return val * val * a;
	}
}

you only need to memory with an array for the problem that you will need almost all previous result, such as calculating the prime number. for this case, you only need to memory one number, just do it with a static var.

Map<Long,ConcurrentHashMap<Long,Long>> memorize =
			Collections.synchronizedMap(new HashMap<Long, ConcurrentHashMap<Long,Long>>());		
	
	public static void main(String[] args) {
		Example1 example=new Example1();
		long start=System.nanoTime();
		System.out.println(example.powerSimple(3,46));
		long end=System.nanoTime();
		System.out.println("simple done in "+ (end-start) );
		
		start=System.nanoTime();
		System.out.println(example.power(3,46));
		end=System.nanoTime();
		System.out.println("memorize done in "+ (end-start) );

	}
	
	public long power(long a, long b){
		if(a==0 )
			return 0;
		if(b==0)
			return 1;
		if(b==1)
			return a;
		
			
		ConcurrentHashMap<Long, Long> values=memorize.get(a);
		if(values==null){
			memorize.put(a, new ConcurrentHashMap<Long, Long>() );
		}
		
		
		Long value=memorize.get(a).get(b);
		if(value!=null)
			return value;
		if(b%2==0){
			value=power(a,b/2) * power(a,b/2);
		}else{
			value=power(a,(b-1)/2) * power(a,(b-1)/2)*a;
		}
		
		memorize.get(a).put(b, value);
		
		return value;
	}
	
	public long powerSimple(long a, long b){
		if(a==0 )
			return 0;
		if(b==0)
			return 1;
		if(b==1)
			return a;
		
		if(b%2==0){
			return power(a,b/2) * power(a,b/2);
		}else{
			return power(a,(b-1)/2) * power(a,(b-1)/2)*a;
		}
		
		
	}

Return:
8500964271916320249
simple power calc done in 679916 nanos
8500964271916320249
memorize power calc done in 46696 nanos

public static int pow(int a, int b) {
	if (b == 0)
		return 0;
	if (b == 1)
		return a;

	// odd exponents?
	Boolean isOddExponent = b % 2 == 1;	
	int orginalBase = a;

	// iteratively square the base (a)
	// and reduce the exponent (b) by half
	// until the exponent is less than 2;
	while (b >= 2) {
		a *= a;
		b /= 2;
	}
	
	// one exponent left?
	if (isOddExponent )
		a *= orginalBase;

	return a;		
}

///
import java.util.HashMap;

public class Snippet {
public static HashMap map = new HashMap();

public static int func(int a, int b) {
if (b == 0)
return -1;
int r = 0;
if (b >= 1) {
if (map.containsKey(a + "" + b)) {
return (int) map.get(a + "" + b);
} else {
if (b % 2 == 0) {
r = func(a, b / 2) * func(a, b / 2);
} else {
r = func(a, b / 2) * func(a, b / 2) * a;
}

}

map.put(a + "" + b, (int)r);
return r;
}

return 1;
}
}
///

def power(a,b):
	if a==0 and n==0:
		return "Math Error!!"
	exponent=b
	number=a
	product=1
	while(exponent>0):
		if exponent%2==0:
			number*=number
			exponent=exponent/2
		else:
			product*= number
			exponent-=1
	return product

def main():
	print power(10,10)
if __name__ == '__main__':
	main()

Basically while raising an integer to the power of the number. You are only multiplying the number by itself at the places where the binary equivalent has a "1".

public static int pow(int x,int y)
    {
        int temp2=x;
        int result=1;
        int temp;
        while((temp=bitcal(y))!=-1)
        {
            if(temp==1)
                result*=temp2;
            temp2*=temp2;y=y/2;
        }
        return result;
    }
    public static int bitcal(int y)
    {
      if(y>=1)
      {     
          y=y%2;     
      }
      else return -1;
      return y;           
    }

The below one goes in one direction (increasing order of power)

/**
 * Created by priganesh on 4/29/14.
 */
public class Memoization {

    int[] previousResult = new int[2];
    public int power(int base, int power) {
        if(power < 0) throw new IllegalArgumentException();
        if(power == 0) return 1;
        if(power == 1) return base;
        System.out.println("Given base : "+base+" Given power : "+power);

        //power is odd
        int result;
        if(power %2 == 1) {
            result = power(base,power/2) * base * power(base,power/2);
        } else {
            result = power(base,power/2) * power(base,power/2);
        }

        return result;
    }

    public int computeFromMemoization(int base, int power) {
        if(power < previousResult[1]) throw new IllegalArgumentException();
        int remainingPower = power - previousResult[1];

        if(previousResult[0] == 0) {
            previousResult[0] = power(base,remainingPower);
        } else {
            //computed from memoized result
            previousResult[0] = previousResult[0] * power(base, remainingPower);
        }

        previousResult[1] = power;

        return previousResult[0];
    }

    public static void main(String[] args) {
        Memoization m = new Memoization();
        int result = m.computeFromMemoization(2,4);
        System.out.println("Result 1 : "+result);

        result = m.computeFromMemoization(2,7);
        System.out.println("Result 2 : "+result);
    }
}

here are we accounting for the fact that a and b has no limitation. Some here are taking a and b as int and also considering all of them as positive.

Iterative O(log(b)) solution. Iterates over bits of b and multiples the result by the amount that corresponds to that bit. Relies on the fact that k^(p+q) = k^p * k^q.

public static long power(int a, int b){ // assumes b is non-negative
		long ret = 1; // result
		long curMult = a; // current multiple
		while( b > 0 ){
			if( (0x1 & b) != 0) ret*=curMult;
			curMult *=curMult;
			b>>>=1;
		}
		return ret;
	}

// Olog(b)
int power(int a, int b)
{
	if(b==0)
		return 1;
	if(a==0)
		return 0;
	int temp= power(a,b/2);
	if(b%2==0)
		return temp*temp;
	else
		return a*temp*temp;
}

Use bit shift to avoid floating point unit for multiplication. Divide the a in a^b such that a is (2^x + y). 2^x is optimized multiplication

public double pow(double x, int n) {
if(n == 0) return 1;
if(n == 1) return x;
if(n ==-1) return 1/x;

double result= x;
long pow = 1;


while(pow*2 < Math.abs(n)){
result = result * result;
pow = pow*2;
}
int remain = Math.abs(n) - (int)pow;
result = result*pow(x, remain);

if(n < 0) result = 1/result;
if( n%2 == 0) result = Math.abs(result);
if(n%2!=0 &&x<0) result = -1*Math.abs(result);
return result;
}

#include<iostream>
using namespace std;

int pow(int x, int y)
{
	if(y  == 0)
		return 1;
	int temp = pow(x,y/2);
	if(y %2 == 0)
		return temp * temp;
	else
	{
		if(y > 0)
			return x * temp * temp;
		else
			return (temp * temp)/x;
	}
}

Use Dynamic programming approch.make a list of lower multiple and combine then to make the desire product.
Suppose ur b=6
then first we find a^2 then from a^2 * a^2 we can make a^4 then from a^4 * a^2 we can make a^6.
just u have to remember till now what you have computed and use those result to find the solution for bigger problem.thats DP.

Binary Exponentiation.

#include <stdio.h>
#define ll long long int

ll f(a,b) {
	if (b == 0)
		return 1;
	if (b == 1)
		return a;
	ll ans = f(a,b/2) * f(a,b/2);
	if (a%b == 1)
		ans *= a;
	return ans;
}

This a O(log(b)) algorithm... or O(k), where k is the number of bits necessary to represent b.

#include <stdio.h>
#define ll long long int

ll f(ll a, ll b) {
	if (b == 0)
		return 1;
	if (b == 1)
		return a;
	ll ans = f(a,b/2) * f(a,b/2);
	if (a%b == 1)
		ans *= a;
	return ans;
}

Iterative solution:

double pow(double x, int n) {
        if(x==0) return 0;
        if(n==0) return 1;
        long long exp = abs(double(n));
        double r=1;
        while(exp){
            if(exp&1)
                r*=x;
            exp>>=1;
            x*=x;
        }
        if(n<0) return 1.0/r;
        return r;
    }

recursive solution:

double pow(double x, int n) {
        if(x==0) return 0;
        if(n==0) return 1;
        double r = pow(x, n/2);
        r*=r;
        if(n%2==1)
            r*=x;
        if(n%2==-1)
            r/=x;
        return r;
    }

public class ApowerB {
	long table[]=new long[1000];
	long findPower(int a, int b)
	{
		if(b==1)
			return a;
		if(b==2)
			return a*a;
		if(table[b/2]==0)
			table[b/2]=findPower(a,b/2);
		if(table[(b+1)/2]==0)
			table[(b+1)/2]=findPower(a,(b+1)/2);
		
		return table[b/2]*table[(b+1)/2];
			
	}
	public static void main(String[] args) {
		ApowerB obj=new ApowerB();
		System.out.println(obj.findPower(3,5));

	}

}

Map<Integer,Integer> memoizationtable = new HashedMap<Integer, Integer>();
	
	
	
	private int recursiveSplit(int a,int b)
	{
		if(b==1)
			return a;
		int leftsplit;
		if(memoizationtable.get(new Integer(b/2))==null)
		{
			leftsplit = recursiveSplit(a, b/2);
			memoizationtable.put(new Integer(b/2), leftsplit);
		}
		else
			leftsplit = memoizationtable.get(new Integer(b/2));
			
		int rightsplit;
		
		if(memoizationtable.get(new Integer(b-b/2))==null)
		{
			rightsplit = recursiveSplit(a,b- b/2);
			memoizationtable.put(new Integer(b-b/2), rightsplit);
		}
		else
			rightsplit = memoizationtable.get(new Integer(b-b/2));
			
		
		return leftsplit * rightsplit;
	}

template <size_t a, size_t b>
struct power{
    enum { value = a * power<a,b-1>::value };
};

template <size_t a>
struct power<a,0>{
    enum { value = 1 };
};

exp(b*ln(a)) -- where a is positive, other cases apply, do your math

Version w/o recursion memory stack:

public static int getPow(int a, int b) {
		int res = a;
		int cache = 1;
		
		while (b/2 > 0) {
			if (b%2 == 1) cache *= res;
			res *= res;
			b/=2;
		}
		res *= cache;
		
		return res;
	}

Shifting is greatly less expensive than the multiplication operation, so if we could convert this into shifting for the most part, we've got ourselves a much cheaper version of the work. Besides, your solution up there don't solve for the power 0 :P

int Power(int a, int b) {
   if (b == 0) {
      return 1;
   }
   int Result = a;
   
   int currentPower = 2;
   while ( b-currentPower > 0) {
       Result <<= 1;
       currentPower <<=1;
   }

   return Result * Power(a, b-currentPower>>1);
}

}