Hello, I need a little help with the correct implementantion of the bisection search algorithm in the following exercise:
- with 2 given variables, balance and annual interest rate, calculate the smallest monthly payment so that we can pay off the balance within a year
test case:
balance = 320000
annualInterestRate = 0.2
below are the provided formulae to use in the problem:
monthly_interest = annualInterestRate / 12
lower_bound = balance / 12
upper_bound = ( balance * ( 1 + monthly_interest)** 12) / 12
here is my code:

new_balance = balance
while new_balance > 0:
    pay = (upper_bound + lower_bound) / 2.0
    for month in range(1,13):
        new_balance = (new_balance - pay) * (1 + monthly_interest) 
        if new_balance < 0:
            lower_bound = pay
            upper_bound = pay
print "Lowest payment: " + str(round(pay,2))          

This is a problem from MIT courseware. I am getting the wrong result 29591.55, where the correct output is
29157.09. I have inserted various print statements which revealed that my upper and lower bounds do not change, so it must be somewthing wrong with my loop conditions but even after a few days of working on this I can't see the mistake, so any help is appreciated. If possible, I want explanations as to what I am doing wrong so I can correct it rather than plain working code, I want to understand it not just solve it


Hello, can you please explain better on this. Im almost there, too. I just cant get the 29157.09 final result. Thanks

No, you have misindented code also. You are quite far. Terminating condition does not depend on new_balance. How did you test your bound logic?

Edited 4 Years Ago by pyTony

Thanks for the reply, I finally did it! I just realized I pasted a wrong code with if conditions inside the for loop when they shouldn't be there.Originally they were placed correctly but I did so many modifications to see what's wrong that I lost track of the intial code..all I had to do was modify that and add an epsilon comparison in my while loop and the balance assignment..I was shocked to see the right answer pop!

Can you please share your final code ?
I got the same results as you 29157.09. and rewrited my code already 10 times :(

Just cannot understand why it is not working

annualInterestRate= 0.2
balance = 3200
epsilon = 0.01
#balance = float(raw_input('Enter balance: '))
#annualInterestRate = float(raw_input('Enter annual rate:'))
monthlyInterestRate = float(annualInterestRate/12.0)
total = balance
low = balance/12
high = (balance*(1+monthlyInterestRate)**12)/12
ans = (low+high)/2
month = 0
total = balance
while abs(total) >= epsilon:
    total = round((total - ans) * (1 + monthlyInterestRate),2)
    while month <12:
        total = round((total - ans) * (1 + monthlyInterestRate),2)
        if total < -0.01:
            high = ans
            low = ans
        ans = float((low + high)/2)
    month += 1

print 'Lowest Payment: ' + str(round(ans,2))

Line 15 termination condition never triggers as month does not change inside the loop, like should be clear from your print.

Edited 4 Years Ago by pyTony

yes, sorry, my bad identation.
I have put it in a loop already.
looks like I have problem after getting negative total.
Thinking about it

My anser is a couple of hundreds greater , wats wrong

   mir = air/12.0 ## air = annualInterestRate
   lower = balance/12.0
   upper = (balance *( 1 +mir)**12)/12.0
   loop = upper
   mp = (lower + upper)/2
   temp = balance
   mi = 0
   flag = 0
   total_debt = balance + (upper *12)
   print ('total debt is' + str(total_debt))
   while temp > 0 :
      temp = balance
      total_debt = balance
      for i in range (1,13):
        mi = (temp - mp) * (mir)
        temp = temp - mp + mi
        total_debt = total_debt + mi
        if temp < 0:
           flag = flag + 1
      if temp> 0.01:
        upper = mp
        lower = mp
      mp = (upper + lower)/2

The temp does not make sense as your variable names are so cryptic I can not wrap my mind around them even I did same code myself.
Line 9 makes even less sense ... ah I understand that you are trying to find the real cost of loan, but that is not asked and that we find at end by counting 12 * minimum_payment, not before finding the minimum payment . Line 6 has however no purpose.

Edited 4 Years Ago by pyTony

temp is being used to calculate balance at the end of year,
Earlier I used abs(total_cost - (12*minimum_payment)) > epsilon as a condition for while loop , but that resulted in an infinite loop

This question has already been answered. Start a new discussion instead.