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

float Legendre(float x, int n)
{
	assert(x >= -1 && x <= 1);
	double ret;
	if (n == 0)
		ret = 1;
	else
	{
		float ppre = 0, pre = 1;
		for (int i = 1; i <= n; ++ i)
		{
			ret = ((2 * i - 1) * x * pre - (i - 1) * ppre) / i;
			ppre = pre;
			pre = ret;
		}
	}
	
	// 下面是為了歸一化起見，使Legendre(x, n) * Legendre(x, n) = 1
	ret *= sqrt((2 * n + 1) / 2);
	
	return ret;
}

std::vector<float> BestLegendre(float* x, float* y, int size, int n)
{
	std::vector<float> alphaVec(n + 1);
	float temp1 = (x[size - 1] - x[0]) / 2;
	float temp2 = (x[size - 1] + x[0]) / 2;
	
	float temp;
	for (int i = 0; i <= n; ++ i)
	{
		for (int j = 0; j < size; ++ j)
		{
			temp = (x[j] - temp2) / temp1;
			alphaVec[i] += Legendre(temp, i) * y[j];
		}
		alphaVec[i] /= size;
	}
	
	return alphaVec;
}