Implementing the bisection algorithm with recursion in Python

Question

I have implemented the Bisection algorithm with Recursion in Python in a toy example in which I aim to find the minimum monthly instalment I should pay each month every month for 12 months so that in the end of the 12 months my balance is zero or slightly less.

Presumable my balance in the beginning of the period is 320000 and the Annual Interest Rate is 0.2. The correct answer is 29157.09.

My code runs into an exception though as it fails to converge.

The code is the following (I have inserted print statements to facilitate debugging)

balance = 320000
annualInterestRate = 0.2

Balance = balance

Annual_interest_rate = annualInterestRate



Monthly_interest_rate = (Annual_interest_rate) / 12.0
Monthly_payment_lower_bound = Balance / 12
Monthly_payment_upper_bound = (Balance * (1 + Monthly_interest_rate)) / 12.0

def bisect(Balance, Annual_interest_rate, a, b ):



    Previous_balance = Balance

    for i in range(12):



            Monthly_unpaid_balance = (Previous_balance) - a
            Updated_balance_each_month = (Monthly_unpaid_balance) + (Monthly_interest_rate * Monthly_unpaid_balance)
            Previous_balance =  Updated_balance_each_month

    f_a = Previous_balance

    for i in range(12):



            Monthly_unpaid_balance = (Previous_balance) - b
            Updated_balance_each_month = (Monthly_unpaid_balance) + (Monthly_interest_rate * Monthly_unpaid_balance)
            Previous_balance =  Updated_balance_each_month

    f_b = Previous_balance

    c = (a + b)/2


    for i in range(12):



            Monthly_unpaid_balance = (Previous_balance) - c
            Updated_balance_each_month = (Monthly_unpaid_balance) + (Monthly_interest_rate * Monthly_unpaid_balance)
            Previous_balance =  Updated_balance_each_month

    f_c = Previous_balance

    print('a is {0}, b is {1}, c = {2}, f_a = {3}, f_b = {4}, f_c = {5}'.format(a, b, c, f_a, f_b, f_c))

    if abs(f_c) <=0.01:
        return(c)

    elif f_c * f_a >0:

        a =c

        print('a is {0}, b is {1}, c = {2}, f_a = {3}, f_b = {4}, f_c = {5}'.format(a, b, c, f_a, f_b, f_c))

        return(bisect(Balance, Annual_interest_rate, a,  b ))

    else:

        b = c

        print('a is {0}, b is {1}, c = {2}, f_a = {3}, f_b = {4}, f_c = {5}'.format(a, b, c, f_a, f_b, f_c))

        return(bisect(Balance, Annual_interest_rate, a,  b ))

When I run the function I get the following printout:

bisect(Balance, Annual_interest_rate, Monthly_payment_lower_bound, Monthly_payment_upper_bound )
a is 26666.666666666668, b is 27111.11111111111, c = 26888.88888888889, f_a = 33328.98239049623, f_b = -322183.0368628964, f_c = -752717.255677314
a is 26666.666666666668, b is 26888.88888888889, c = 26888.88888888889, f_a = 33328.98239049623, f_b = -322183.0368628964, f_c = -752717.255677314
a is 26666.666666666668, b is 26888.88888888889, c = 26777.77777777778, f_a = 33328.98239049623, f_b = -319209.06882307003, f_c = -747603.8415428438
a is 26666.666666666668, b is 26777.77777777778, c = 26777.77777777778, f_a = 33328.98239049623, f_b = -319209.06882307003, f_c = -747603.8415428438
a is 26666.666666666668, b is 26777.77777777778, c = 26722.222222222226, f_a = 33328.98239049623, f_b = -317722.08480315685, f_c = -745047.1344756087
a is 26666.666666666668, b is 26722.222222222226, c = 26722.222222222226, f_a = 33328.98239049623, f_b = -317722.08480315685, f_c = -745047.1344756087

pjs pjs · Accepted Answer · 2018-07-15T18:12:40

The following uses a front-end function so the user doesn't have to deal with "magic" parameters such as your a and b. It rescales the annual interest rate to a monthly rate, and converts the calculations to integer by scaling the recursion input by 100, then rescaling the solution before returning it.

def calculate_payment(balance, interest):
    balance = int(100 * balance)
    return bisect(balance, interest / 12.0, 0, balance) * 0.01

def bisect(balance, monthly_interest, low, high):
    payment = round((high + low) / 2)
    remaining_balance = balance
    for _ in range(12):
        remaining_balance -= payment
        remaining_balance += int(monthly_interest * remaining_balance)
    if remaining_balance > 0:
        return bisect(balance, monthly_interest, payment, high)
    elif remaining_balance <= -12:
        return bisect(balance, monthly_interest, low, payment)
    else:
        return payment

print(calculate_payment(320000.00, 0.2))

Implementing the bisection algorithm with recursion in Python

1 Answers