#Program to interpolate using newton backward interpolation

Below is the implementation of newton backward interpolation method.

#Program to interpolate using newton backward interpolation

# calculating u mentioned in the formula
def u_cal( u, n) :
    temp = u
    for i in range (1,n):
        temp = temp * (u + i)
    return temp


#calculating factorial of given number n
def fact(n) :
    f = 1
    for i in range (2,n):
        f *= i
    return f

# Number of values given
from array import *
n = 5
x= [1891,1901,1911,1921,1931 ]
#y[][] is used for difference table with y[][0] used for input
y= [ [46 , 0.0, 0.0, 0.0, 0.0, 0.0 , 0.0] ,
     [66 , 0.0, 0.0, 0.0, 0.0, 0.0 , 0.0] ,
     [81 , 0.0, 0.0, 0.0, 0.0, 0.0 , 0.0] ,
     [93 , 0.0, 0.0, 0.0, 0.0, 0.0 , 0.0] ,
     [101, 0.0, 0.0, 0.0, 0.0, 0.0 , 0.0] ]

# Calculating the backward difference table
for i in range (1,n):
    # print(i,'->',end='') #for debug
    for j in range (n-1,i-1,-1):
        #print(j,end='') #for debug
        y[j][i] = (y[j][i - 1] - y[j - 1][i - 1])
    #print('\n') #for debug
 
# Displaying the backward difference table
for i in range (0,n):
    for j in range (0,i+1):
        print(y[i][j],'\t',end='')
    print('\n')


# print(y) # for debug
#Value to interpolate at
value = 1925;
 
#Initializing u and sum
sum = y[n - 1][0]
u = (value - x[n - 1]) / (x[1] - x[0])
for i in range (1,n):
    sum = sum + (u_cal(u, i) * y[n-1][i]) / fact(i)

print('\n Value at', value ,' is ',sum )

'''
Output:

  46   
  66      20   
  81      15      -5   
  93      12      -3       2   
 101       8      -4      -1      -3   

 Value at 1925 is 96.8368
 '''