CareerCup

#include <limits>
#include <utility>
#include <algorithm>
#include <iostream>
#include <cmath>

/*	
	That's the story (took roughly more than 45 minutes...)

	result = base ^ exponent, where the exponent is double (meaning e.g. 2.14 ^ 10.1241 or -2.14 ^ -1.42 
	which is a complex number)

	I can't cover all the special cases, such as -inf + inf, NaN, negative base and negative exponent, 
	so I just assume base and exponent are positivie... it's complicated enough

	1) if the exponent is an integer it's easy base^8 = ((base^2)^2)^2 (note 3 instead 8 multiplications, 
	   roughly lg(exp) multiplications

	2) if the exponent has a decimal part e.g. base^8.5 we can write: base^(8+1/2) = base^8 * base^(1/2) 
	   (base^1/2 is the square-root of base, base^1/4 is the 4-th root of base etc...)
	   so after powering the integer part, we multiply it with the power of the decimal part.

	   powering the decimal part rquires us to have a root. root can be self-made by using newton method. 
	   newton method requires a good guess to converge and to not take long. a good guess can be done using 
	   binary search in the number range.

	   note we can write the decimal part of the power as base^dec_exponent = base^0.33333 (e.g.)
	   which is base^(0.25 + 0.0625 + 0.015625 + ...)
	   which is base^(1/4 + 1/16 + 1/64)
*/

// power with integer exponent
double mypow(double base, unsigned int exp) 
{
	if (exp == 0) return 1;
	if (exp == 1) return base;
	if (exp == 2) return base*base;
	double result = mypow(base, static_cast<unsigned int>(exp / 2));
	result *= result;
	if (exp % 2 == 1) result *= base;
	return result;
}

// takes the square root based on binary search (could use newton method, too)
double mysqrt(double value)
{
	if (value == 0) return value;

	// guess x using "binary search" to get close 
	double lo = 0.0; // root of something never get's below 0
	double hi = value;
	double x = (hi + lo) / 2;
	while (abs(hi - lo) > 0.001)
	{
		x = (hi + lo) / 2;
		double res = x * x;
		if (res > value) hi = x;
		else lo = x;
	}

	// with the reasonable accurate guess perform newton methode
	for(int i = 0; i < 20; i++)
	{
		x = x - ((x*x - value) / (2 * x));
	}

	return x;
}

// powerfunction as desired by the question
double mypow(double base, double exp) 
{
	if ((exp < 0) && (base < 0) && (exp - static_cast<int>(exp) > 0.0)) throw "no support for complex numbers";
	if (exp < 0) return 1.0 / mypow(base, -exp); // negative exponent is just 1/pow(base, -exp)

	double result = mypow(base, static_cast<unsigned int>(exp)); // power integer part
	double expdec = exp - static_cast<unsigned int>(exp); // remove integer part from exponent: 0 <= expdec < 1
	if (expdec >= 1.0) throw "exponent too high";

	if (expdec > 0.0)
	{
		double epsilon = 0.000000000000001;
		double currentRs = 1.0;
		double currentRt = mysqrt(base);
		double currentExp = 0.5;
		double remainingExp = expdec;

		while (remainingExp > epsilon && currentExp > epsilon)
		{
			if (remainingExp >= currentExp)
			{
				currentRs *= currentRt;
				remainingExp -= currentExp;
			}
			currentRt = mysqrt(currentRt);
			currentExp /= 2;
		}

		result *= currentRs;
	}
	return result;
}

// test helper function
void testMyPow(double base, double exp)
{
	double myresult = mypow(base, exp);
	double result = pow(base, exp);
	double error = abs(myresult - result);
	std::cout << "tested " << base << "^" << exp << " mypow returned " << myresult << " pow returned " << result << " error " << error << std::endl;
}

int main()
{
	testMyPow(2.0, 20.0);
	testMyPow(2.0, -5.0);
	testMyPow(2, 1.5);
	testMyPow(0.212, 91.231);
	testMyPow(891.212, 0.33333333333);
    return 0;
	/* output 
	tested 2^20 mypow returned 1.04858e+06 pow returned 1.04858e+06 error 0
	tested 2^-5 mypow returned 0.03125 pow returned 0.03125 error 0
	tested 2^1.5 mypow returned 2.82843 pow returned 2.82843 error 0
	tested 0.212^91.231 mypow returned 3.47494e-62 pow returned 3.47494e-62 error 2.59085e-77
	tested 891.212^0.333333 mypow returned 9.62337 pow returned 9.62337 error 3.55271e-15	
	*/
}

double ans = 1;
		for (int i=1; i<=power; i++)
			ans = ans * x;

double ans = 1;

for (int i=1; i<=power; i++)

ans = ans * x;

double ans = 1;for (int i=1; i<=p; i++)	ans = ans * x; System.out.println("Ans : " + ans);

double ans = 1; for (int i=1; i<=p; i++) ans = ans * x;System.out.println("Ans : " + ans);