CareerCup

What are the allowed functions/operations?
You can do power with only plus (so 0 multiplication)

double power(double x, unsigned int n)
{
   if (!n) return 1.0;
   if (n == 1) return x;
   double result = power(x, n/2);
   result *= result;
   return (n&1) ? result*x : result;
}

// forgot to login :)
double power(double x, unsigned int n)
{
   if (!n) return 1.0;
   if (n == 1) return x;
   double result = power(x, n/2);
   result *= result;
   return (n&1) ? result*x : result;
}

In the best case when n is a power of 2, we need to use log(n) times, otherwise (the worst case) 2*log(n).

type y=1;

while( N )
{
   if( N&1 )
     y*=X;

   X*=X;
   N>>=1;

}

return y;

The following solution computes it using floor(log(n)) multiplications.

double power(double x, unsigned int n) {
double res = 1.0;
double m = x;

if (x == 0.0)
return 0.0;

while (n) {
if (n & 1)
res *= m;

m *= m;
n >>= 1;
}

return res;
}

if n is a power of 2 then it will take logn+1
if not it will take max 2*(logn)+1
if u add one statement within if that is
if(n==1)
break;

it reduces one more multiplication
because we are trying to reduce number of multiplications

double powerofN(double num, unsigned int power)
{
double reminder=1;
if( power < 1)
return 1;
while(power > 1)
{
if(power%2 ==0 )
{
num = num * num;
power = power/2;
}
else
{
reminder = reminder * num;
num = num * num;
power = (power - 1)/2;
}
}
num = num * reminder;
// printf("The value of num is %f and result is %f\n", num, result);
return num;
}

#include <vector>
#include <math.h>
#include <iostream>

using namespace std;

int main(){

	int x = 2;
	int n = 15;

	//compute pow(x,n)
	//In this case the algorithm computes in atmost ceil(2 * (logn base2))+1 computations
	vector <long> arr;
	arr.push_back(x);
	int baseComputs,numOfComputs = 0;
	long result = 1;
	
	baseComputs = floor(log2(n));
	int i=1;
	for (;i<=baseComputs;i++){
		arr.push_back(arr[i-1]*arr[i-1]);numOfComputs++;
		if(n&(1<<i-1)){
			result=result*arr[i-1];numOfComputs++;
		}
	}
	if(n&(1<<i-1)){
		result=result*arr[i-1];numOfComputs++;
	}

	cout << "pow("<<x<<","<<n<<") is :: "<<result<<". with "<<numOfComputs<<" multiplications"<<endl;
	return 1;
}

<pre lang="" line="1" title="CodeMonkey73107" class="run-this">public class Power {

public static int power(int base, int power) {
int res = 1;
if (power > 0) {
int mask = 0x1;
while (mask <= power) {
if ((mask & power) != 0) {
res *= base;
}
mask <<= 1;
base *= base;
}
}
return res;
}

public static void main(String[] args) {
System.out.println(Power.power(3, 6));
System.out.println(Power.power(5, 4));
System.out.println(Power.power(6, 4));
System.out.println(Power.power(10, 7));
}
}
</pre>