// Arup Guha
// 2/10/2012
// Example illustrating the Divided Difference Technique from 3.3
#include <stdio.h>

#define SIZE 100

// Function that prints the divided differences.
void printDifferences(double xVals[], double yVals[], int length);

int main() {

    // Test case from the textbook.
    double x[] = {1.0, 1.3, 1.6, 1.9, 2.2};
    double y[] = {.7651977, .620086, .4554022, .2818186, .1103623};

    printDifferences(x, y, 5);

    return 0;

}

void printDifferences(double xVals[], double yVals[], int length) {

    // This will store all the differences.
    double differences[SIZE][SIZE];

    // Fail case, algorithm won't run.
    if (length > SIZE)
        return;

    // Seed our table with the function values.
    int i;
    for (i=0; i<length; i++)
        differences[0][i] = yVals[i];

    // Go through each rol and column in the table.
    int row, col;
    for (row=1; row<length; row++) {

        // Just take the difference of terms on the previous row.
        for (col=0; col<length-row; col++) {
            differences[row][col] = (differences[row-1][col+1] - differences[row-1][col])/(xVals[row+col]-xVals[col]);
        }
    }

    // Now we can print the chart.
    for (row = 0; row<length; row++) {

        for (col = 0; col<length-row; col++) {
            printf("%f\t", differences[row][col]);
        }
        printf("\n");
    }
}