Bisection search implementation

[Eridanus]

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
        else:
            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

Cheers

[TrustyTony]

Use same kind of epsilon and absolute value 'floating point equality test' with zero to finish as in the lecturers root finding example (which I generalized little in http://www.daniweb.com/software-development/python/code/436392/example-of-bisection-search-for-monotonously-increasing-function-value)

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

[TrustyTony]

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?

[Eridanus]

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!

[Dorian123]

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

[TrustyTony]

After Oct 15 return day. Take my hint earlier in thread.

[Dorian123]

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)
        print('month',month,'lower',round(low,2),'upper:',round(high,2),total,round(ans,2))        
        if total < -0.01:
            high = ans
        else:
            low = ans
        ans = float((low + high)/2)
    month += 1

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

[TrustyTony]

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

[Dorian123]

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

[TrustyTony]

Anything strange in line 11 or lines 14 vs 16?

[amRx1]

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
           break
      if temp> 0.01:
        upper = mp
      else:
        lower = mp
      mp = (upper + lower)/2

[TrustyTony]

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.

[amRx1]

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