# math AAT (Alternative Assessment Tool)
# python math project - chapter 2 - numerical methods
# Newton's Backward Interpolation Formula
# 18th October, 2015

import time

diff_file = open('NewtonBIF.txt', 'w')
diff_file.close()


def factorialfunc(n):
    '''
    Returns the factorial of a positive integer.
    '''
    assert type(n) == type(1) or type(n) == type(1.0), "n is not a number."
    n = int(n)
    assert n > 0, "Can not find factorial of a negative number."
    if n == 1:
        return 1
    else:
        return n * factorialfunc(n-1)


def diffgen(diff_file):
    '''
    Finds the first, second, third (and so on) difference of given y values.
    '''
    print('\nCreating difference table for difference 1')
    # time.sleep is used to make output on terminal more pleasant
    time.sleep(1)
    diff_file = open('NewtonBIF.txt', 'r')
    filevals = list(diff_file.readlines()[-1].split())
    diffvals = [(float(filevals[i+1]) - float(filevals[i])) for i in range(len(filevals) - 1)]
    # prints diffvals
    for val in diffvals:
        print(val)
    diff_file = open('NewtonBIF.txt', 'a')
    diff_file.writelines([" ".join(str(val) for val in diffvals)])
    diff_file.write('\n')
    iternum = len(filevals) - 2  # 1 because it has been done above
    for i in range(iternum):
        print('\nCreating difference table for difference {}'.format(i+2))
        time.sleep(1)
        diff_file = open('NewtonBIF.txt', 'r')
        filevals = list(diff_file.readlines()[-1].split())
        diffvals = [(float(filevals[i+1]) - float(filevals[i])) for i in range(len(filevals) - 1)]
        # prints diffvals
        for val in diffvals:
            print(val)
        diff_file = open('NewtonBIF.txt', 'a')
        diff_file.writelines([" ".join(str(val) for val in diffvals)])
        diff_file.write('\n')
        diff_file.close()
    print('\n')


def genpterm(p, iternum, ynterms):
    '''
    Generates the value of p term for terms in the main equation.
    '''
    pterm = 1
    print('\nCalculating pterm of {} term'.format(iternum + 2))
    for i in range(iternum+1):
        print('\tpterm = {} * ({} - {})'.format(pterm, p, i))
        pterm *= p + i
        print('\tpterm is {}'.format(pterm))
    return pterm


def ypgen(diff_file, p):
    '''
    Calculates value of yp by finding and adding all the terms.
    '''
    diff_file = open('NewtonBIF.txt', 'r')
    content = diff_file.readlines()
    ynterms = []
    for i in content:
        ynterms.append(i.split()[-1])
    ynterms = [float(term) for term in ynterms]
    yp = ynterms[0]
    ynterms = ynterms[1:]
    iternum = len(ynterms)
    print('\nAs p = {}'.format(p))
    for i in range(iternum):
        print("\n")
        print('{} term of yp is (pterm * {}) / {}!'.format(i + 2, ynterms[i], i + 1))
        time.sleep(1)
        yp += float(genpterm(p, i, ynterms) * ynterms[i]) / float(factorialfunc(i+1))
    print('returning yp = {}'.format(yp))
    diff_file.close()
    return yp


def main():
    print("What is the number of values of x?")
    n = int(raw_input())
    print('\n')
    h = raw_input('Are the values equally spaced?\nIf yes enter value of \'h\'. If no, press \'n\': ')
    if h == 'n':
        print("Newton's Backward Interpolation Formula can not be applied.\nExiting program.")
        exit()
    else:
        try:
            h = float(h)
        except:
            h = raw_input('Please enter a valid number for h. ')
            while type(h) != type(1.0) and type(h) != type(1):
                h = raw_input('Please enter a valid number for h. ')
                try:
                    h = float(h)
                except:
                    pass
    x0 = float(raw_input('Enter value of x0. '))
    xvals = [(x0 + (i * h)) for i in range(n)]
    print("The values of x are: ")
    for i in xvals:
        print(i),
    print('\n')
    xn = xvals[-1]
    xp = float(raw_input('Enter the value of xp. '))
    print("Finding the value of p.")
    print("Using the formula xp = xn + ph")
    print("Here {} = {} + p * {}".format(xp, xn, h))
    p = (float(xp - xvals[-1])) / float(h)
    print('Value of p is: {}'.format(p))
    print('Values of x are ', xvals)
    yvals = [None] * n
    for i in range(n):
        ytemp = float(raw_input('Enter value of y{}: '.format(i)))
        yvals[i] = ytemp
    with open('NewtonBIF.txt', 'a') as diff_file:
        diff_file.write(' '.join([str(val) for val in yvals]))
        diff_file.write('\n')
    print('\nValues of y are {}'.format(yvals))
    xtoymap = {}
    for i in range(n):
        xtoymap[xvals[i]] = yvals[i]
    print('\nx values & corresponding y values are:')
    print('\nx values            y values')
    for key in xvals:
        print('\n{}                 {}'.format(key, xtoymap[key]))
    diff_file = open('NewtonBIF.txt', 'a')
    diffgen(diff_file)
    diff_file.close()
    yp = ypgen(diff_file, p)
    decimalval = int(raw_input('\n\nHow many decimal digits accuracy do you want\nfor the value of yp = y({}): '.format(xp)))
    yp = round(yp, decimalval)
    print('Value of yp = y({}) = {}'.format(xp, yp))
    print('\n')
    print("See NewtonBIF.txt for y difference values.")
    print('\n\n\n')


if __name__ == '__main__':
    main()

# math AAT (Alternative Assessment Tool)
# python math project - chapter 2 - numerical methods
# Newton's Backward Interpolation Formula
# 18th October, 2015

import time

diff_file = open('NewtonBIF.txt', 'w')
diff_file.close()


def factorialfunc(n):
    '''
    Returns the factorial of a positive integer.
    '''
    assert type(n) == type(1) or type(n) == type(1.0), "n is not a number."
    n = int(n)
    assert n > 0, "Can not find factorial of a negative number."
    if n == 1:
        return 1
    else:
        return n * factorialfunc(n-1)


def diffgen(diff_file):
    '''
    Finds the first, second, third (and so on) difference of given y values.
    '''
    print('\nCreating difference table for difference 1')
    # time.sleep is used to make output on terminal more pleasant
    time.sleep(1)
    diff_file = open('NewtonBIF.txt', 'r')
    filevals = list(diff_file.readlines()[-1].split())
    diffvals = [(float(filevals[i+1]) - float(filevals[i])) for i in range(len(filevals) - 1)]
    # prints diffvals
    for val in diffvals:
        print(val)
    diff_file = open('NewtonBIF.txt', 'a')
    diff_file.writelines([" ".join(str(val) for val in diffvals)])
    diff_file.write('\n')
    iternum = len(filevals) - 2  # 1 because it has been done above
    for i in range(iternum):
        print('\nCreating difference table for difference {}'.format(i+2))
        time.sleep(1)
        diff_file = open('NewtonBIF.txt', 'r')
        filevals = list(diff_file.readlines()[-1].split())
        diffvals = [(float(filevals[i+1]) - float(filevals[i])) for i in range(len(filevals) - 1)]
        # prints diffvals
        for val in diffvals:
            print(val)
        diff_file = open('NewtonBIF.txt', 'a')
        diff_file.writelines([" ".join(str(val) for val in diffvals)])
        diff_file.write('\n')
        diff_file.close()
    print('\n')


def genpterm(p, iternum, ynterms):
    '''
    Generates the value of p term for terms in the main equation.
    '''
    pterm = 1
    print('\nCalculating pterm of {} term'.format(iternum + 2))
    for i in range(iternum+1):
        print('\tpterm = {} * ({} - {})'.format(pterm, p, i))
        pterm *= p + i
        print('\tpterm is {}'.format(pterm))
    return pterm


def ypgen(diff_file, p):
    '''
    Calculates value of yp by finding and adding all the terms.
    '''
    diff_file = open('NewtonBIF.txt', 'r')
    content = diff_file.readlines()
    ynterms = []
    for i in content:
        ynterms.append(i.split()[-1])
    ynterms = [float(term) for term in ynterms]
    yp = ynterms[0]
    ynterms = ynterms[1:]
    iternum = len(ynterms)
    print('\nAs p = {}'.format(p))
    for i in range(iternum):
        print("\n")
        print('{} term of yp is (pterm * {}) / {}!'.format(i + 2, ynterms[i], i + 1))
        time.sleep(1)
        yp += float(genpterm(p, i, ynterms) * ynterms[i]) / float(factorialfunc(i+1))
    print('returning yp = {}'.format(yp))
    diff_file.close()
    return yp


def main():
    print("What is the number of values of x?")
    n = int(raw_input())
    print('\n')
    h = raw_input('Are the values equally spaced?\nIf yes enter value of \'h\'. If no, press \'n\': ')
    if h == 'n':
        print("Newton's Backward Interpolation Formula can not be applied.\nExiting program.")
        exit()
    else:
        try:
            h = float(h)
        except:
            h = raw_input('Please enter a valid number for h. ')
            while type(h) != type(1.0) and type(h) != type(1):
                h = raw_input('Please enter a valid number for h. ')
                try:
                    h = float(h)
                except:
                    pass
    x0 = float(raw_input('Enter value of x0. '))
    xvals = [(x0 + (i * h)) for i in range(n)]
    print("The values of x are: ")
    for i in xvals:
        print(i),
    print('\n')
    xn = xvals[-1]
    xp = float(raw_input('Enter the value of xp. '))
    print("Finding the value of p.")
    print("Using the formula xp = xn + ph")
    print("Here {} = {} + p * {}".format(xp, xn, h))
    p = (float(xp - xvals[-1])) / float(h)
    print('Value of p is: {}'.format(p))
    print('Values of x are ', xvals)
    yvals = [None] * n
    for i in range(n):
        ytemp = float(raw_input('Enter value of y{}: '.format(i)))
        yvals[i] = ytemp
    with open('NewtonBIF.txt', 'a') as diff_file:
        diff_file.write(' '.join([str(val) for val in yvals]))
        diff_file.write('\n')
    print('\nValues of y are {}'.format(yvals))
    xtoymap = {}
    for i in range(n):
        xtoymap[xvals[i]] = yvals[i]
    print('\nx values & corresponding y values are:')
    print('\nx values            y values')
    for key in xvals:
        print('\n{}                 {}'.format(key, xtoymap[key]))
    diff_file = open('NewtonBIF.txt', 'a')
    diffgen(diff_file)
    diff_file.close()
    yp = ypgen(diff_file, p)
    decimalval = int(raw_input('\n\nHow many decimal digits accuracy do you want\nfor the value of yp = y({}): '.format(xp)))
    yp = round(yp, decimalval)
    print('Value of yp = y({}) = {}'.format(xp, yp))
    print('\n')
    print("See NewtonBIF.txt for y difference values.")
    print('\n\n\n')


if __name__ == '__main__':
    main()

# math AAT (Alternative Assessment Tool) # python math project - chapter 2 - numerical methods # Newton's Backward Interpolation Formula # 18th October, 2015 Returns the factorial of a positive integer. Finds the first, second, third (and so on) difference of given y values. # time.sleep is used to make output on terminal more pleasant # prints diffvals # 1 because it has been done above # prints diffvals Generates the value of p term for terms in the main equation. Calculates value of yp by finding and adding all the terms.