#include <math.h>
#include "main.h"
#include <stdlib.h>
#include <stdio.h>
#include "metod_03.h"

int k = 1;
double *d = NULL;
double *dop = NULL;

void Coeff_01(int n, double *x, double *f_x, double *c);
double Value_01(double t, int n, double *c, double *x);

void Coeff_01(int n, double *x, double *f_x, double *c)
{
	int i, j;

	for (i = 0; i < n; i++) {
		c[i] = f_x[i];
        dop[i] = f_x[i];
    }

	for (i = 1; i < n; i++)
		for (j = n - 1; j > i - 1; j--)
			c[j] = (c[j] - c[j - 1]) / (x[j] - x[j - i]);
}

double Value_01(double t, int n, double *c, double *x)
{
	int i;
	double fx;

	fx = c[n - 1];

	for (i = n - 2; i >= 0; i--)
	{
		fx *= (t - x[i]);
		fx += c[i];
	}

	return fx;
}

void Coeff_03(int n, double *x, double *f_x, double *c);
void Coeff_03(int n, double *x, double *f_x, double *c){
	d = (double*)malloc((k + 1) * sizeof(double));
	dop = (double*)malloc(n * sizeof(double));
	Coeff_01(n, x, f_x, c);
}

double Value(double t, int n, double *c, double *x, int m);
double Value(double t, int n, double *c, double *x, int m) {
    double fx;
    int i;
    int l = 1;
    fx = c[n - 1];
	for (i = n - 2; i >= m; i--)
	{
		fx *= (t - x[i - m]);
		fx += c[i];
	}

    for (i = 2; i <= m; i++) {
        l = l * i;
    }

    return l * fx;
}

double Value_03(double t, int n, double *c, double *x);
double Value_03(double t, int n, double *c, double *x)
{
	int i, j, m;
    d[0] = Value_01(t, n, c, x);


    c[0] = d[0];
    for (i = 1; i < n; i++) {
        c[i] = dop[i - 1];
    }

    for (i = 1; i < n; i++)
        for (j = n - 1; j > i - 1; j--) {
	    if (fabs(x[j] - t) < 1e-3) {
		printf("%lf\n", x[j] - t);
		return t;
	    }
	    else {
		c[j] = (c[j] - c[j - 1]) / (1e5 * (x[j] - t));
	    }
        }

    d[1] = Value(t, n, c, x, 1);

    for (m = 2; m <= k; m++) {

        for (j = m; j < n; j++) {
            if (j == m) {
                c[j] = (c[j - 1] - d[j - 1]) / (x[j] - t);
                c[j - 1] = d[j - 1];
            } else {
                c[j] = (c[j] - c[j - 1]) / (x[j] - t);
            }
        }
        d[m] = Value(t, n, c, x, m);
    }
    return d[0];
}