long long factorial(long n)
{
	return (n == 1 || n == 0) ? 1 : factorial(n - 1) * n;
}

double calculateCoefficient(int m, int n, long long factor)
{
	int firstTerm = m % 2 == 0 ? 1 : -1;

	long long secondTermNumerator = factorial(n);
	long long secondTermDenominator = factorial(2 * n);

	long long thirdTermNumerator = factorial(2 * n - 2 * m);
	long long thirdTermDenominator = factorial(m) * factorial(n - m) * factorial(n - 2 * m);
	long long thirdTerm = thirdTermNumerator / thirdTermDenominator;

	long long numerator = factor * secondTermNumerator * thirdTerm; // 128 is the max integral denominator up to P8
	long long denominator = secondTermDenominator;


	double resultDouble = firstTerm * (double)numerator / (double)denominator;

	return resultDouble;
}

vector<double> calculateCoefficients(int n, long long factor)
{
	int M;
	if (n % 2 == 0){ M = n / 2; }
	else{ M = (n - 1) / 2; }

	vector<double> coeff(M + 1);
	for (int m = 0; m <= M; m++)
	{
		coeff[m] = calculateCoefficient(m, n, factor);
	}
	return coeff;
}

double poly(int n, double x, long long factor)
{
	int M;
	if (n % 2 == 0){ M = n / 2; }
	else{ M = (n - 1) / 2; }
	vector<double> coeff(M + 1);
	for (int m = 0; m <= M; m++)
	{
		coeff[m] = calculateCoefficient(m, n, factor);
	}

	double y = 0.0;
	for (int i = 0; i <= M; i++)
	{
		y += pow(x, n - 2 * i)*coeff[i];
	}
	return y;
}

int calculateNormalizationFactor(int n)
{
	if (n == 0 || n == 1) return 1;
	return (2 * n - 1) * calculateNormalizationFactor(n - 1);
}

int signOfValue(double val)
{
	// http://stackoverflow.com/questions/1903954/is-there-a-standard-sign-function-signum-sgn-in-c-c
	return (val > 0) - (val < 0);
}