/**
*@file exercice4.c
*@author Alain CHRISTMANN
*@author Daniel CALECA
*@date 28.03.2007
*@version 1.00
*
*Programmation de la methode de Newton
*/

#include <stdio.h>
#include <math.h>

//calcul du polynome d'apres le schema de horner
float calcPoly(float *coefs, int degres, float x)
{
    int i;
    float poly = coefs[0];
    
    for (i = 1; i <= degres; i++)
    {
        poly = poly * x + coefs[i];
    }
    
    return poly;
}


float calcDeriv(float *coefs, int degres, float x, int derivee)
{
    int i, j;
    
    //calcul des coefficients du polynome derive
    for (i = 0; i < derivee; i++)
    {
        for (j = 0; j <= degres; j++)
        {
            coefs[j] = coefs[j] * (degres - j);
        }
    }

    if (degres - derivee < 0)
        return 0;
    else
        return calcPoly(coefs, degres - derivee, x);
}


float polyDeTest(float x, int derivee)
{
    float coefs[4] = { -1, 8, -17, 11 };    //Ici, la fonction de test est -x^3+8x^2-17x+11
    return calcDeriv(coefs, 3, x, derivee); //Le deuxieme parametre indique le degre du polynome.
}


float fonction(float x)
{
    return polyDeTest(x, 0);
}


float derivee(float x)
{
    return polyDeTest(x, 1);
}

/*
float fonction(float x)
{return sqrt(x);}

float derivee(float x)
{return 1/(2*sqrt(x));}
*/

float newton(float fonction(float x), float derivee(float x), float precision, float debut, int maxiter)
{
    int iter = 1;   //iteration en cours
    float valDerivee;
    float xPrecedent;

    valDerivee = derivee(debut);

    // test de derivee non nulle
    if (fabs(valDerivee) > 0.000001)
    {
        xPrecedent = debut;
        debut = debut - fonction(debut) / valDerivee;
    }
    // derivee nulle, on reprend un peu plus loin        
    else
    {
        xPrecedent = debut;
        debut = debut + precision * 100;
    }
    while (fabs(debut - xPrecedent) > precision * (fabs(debut) + 0.1) && iter <= maxiter)
    {
        valDerivee = derivee(debut);
        
        // test de derivee non nulle
        if (fabs(valDerivee) > 0.000001)
        {
            xPrecedent = debut;
            debut = debut - fonction(debut) / valDerivee;
        }
        // derivee nulle, on reprend un peu plus loin        
        else
        {
            xPrecedent = debut;
            debut = debut - precision * 100;
        }
        iter = iter + 1;
    }
    
    printf("nombre d'iterations : %d\n", iter);
    
    return debut;
}

int main()
{
    float debut;
    float precision;
    float resultat;
    int maxiter;

    printf("entrez le debut du test: ");
    scanf("%f", &debut);
    printf("entrez la precision: ");
    scanf("%f", &precision);
    printf("entrez le nombre d'iterations maximum: ");
    scanf("%d", &maxiter);

    resultat = newton(fonction, derivee, precision, debut, maxiter);
    printf("racine trouvee: %f\n", resultat);

    return (0);
}