Computing the lowest monthly payment using bisection search in python

Question

I'm trying to compute the minimum monthly payment to pay off a loan using the following:

balance = 999999
annualInterestRate = .18
monthlyInterestRate = annualInterestRate/12

balanceCOPY = balance

#Bisection search parameters

lo = balance/12
hi = (balance*(1+monthlyInterestRate**12))/12
epsilon = .01

guess = (lo + hi)/2

while True:
   for month in range(1,13):
      balance = balance - guess
      balance = balance + (monthlyInterestRate*balance)

   if balance > 0 and balance > epsilon:
      lo = guess
      balance = balanceCOPY
   elif balance < 0 and balance < -epsilon:
      hi = guess
      balance = balanceCOPY
   else:
      print('Lowest payment: ',str(round(guess,2)))
      break

   guess = (lo + hi)/2

However, I seem to be stuck in some sort of infinite loop where my guess variable is not being updated. How can I break out of the infinite loop and have my guess variable updated?

The problem was in my math. I meant to say

hi = (balance*(1+monthlyInterestRate)**12)/12

Thank you for all the help everyone!

Answer 1

First of all, if you are doing MITx exercise and completed the previous test (just to increment 10 in guess) you're a little step to get it. Just need some adjustments on while condition and check about the annual results.

About bisection search I'll try to clarify the concept. You'll always have two extremities, the minimum and the maximum. And will always start guessing by the middle of the extremities.

After the first guess, you'll need to adjust the extremities due the annual results. If after one year paying the minimum for drinks, girls, program books and other things you didn't pay the total balance, you certainty need to increase the minimum. Otherwise If, for example, you payed the total balance in the 10th month, you need to drink more and meet new girls next year!!! just kidding... you need do decrease the minimum. This is the check you need to do after completed one year of hard payments

---

In the exercise, we have:

• balance and annualInterestRate = given (we don't need to care)
• minimum (lower bound) = Balance / 12
• maximum (upper bound) = (Balance x (1 + Monthly interest rate)**12) / 12.0

The first guess will be (minimum + maximum) /2 I called guessMinimum so:

guessMinimum = (minimum + maximum)/2

So you'll start using the first guess (guessMinimum). After one year you'll check the remain. If the remain is negative, means that you have paid too much. you need to decrease the monthly payment. Otherside, if after one month the remain is positive (for example, more than your precision (ex. 0.10)) you need to decrease the monthly payment, okay?!

Trying to design the thinking.....

 +------------------------------------------------+ 
 |   /\                  /\                   /\  | 
 |   \/------------------\/-------------------\/  | 
 |MINIMUM               guess              MAXIMUM| 
 |                     Minimum                    | 
 +------------------------------------------------+ 

If after one year, the "remain" is negative (for example). Means that the 'guessMinimum' is to much!!! You'll need... not you, the PROGRAM!! The program need to adjust it, lower the minimum so......

 +---------------------------------------------------+ 
 |                        Got negative 'remain'      | 
 |                   ++                              | 
 |    /\             ||   /\                   /\    | 
 |    \/-------------||---\/-------------------\/    | 
 | MINIMUM           ||  guess              MAXIMUM  | 
 |                   ++ Minimum-,                    | 
 |                               ',                  | 
 |                                 `.                | 
 |                                   `.,             | 
 |                                      ',           | 
 |                                        ',         | 
 |                                          `.       | 
 |                                            `      | 
 |    /\                  /\                   /\    | 
 |    \/------------------\/-------------------\/    | 
 | MINIMUM               guess              MAXIMUM  | 
 +---------------------------------------------------+ 

Sorry guys. I tried to insert an image but as a new member. I couldn't. need at least 10 reputation.... help me!!!! too much work to use characters!!!!

And the CODE need to do this hard work to adjust the minimum until the 'remain' is acceptable (within your precision, or epsilon, or any letter or variable or.. okay. :)

After understanding the concept and drawings.. let's check the CODE.

balance = 999999; 
annualInterestRate = 0.18

monthlyInterestRate = annualInterestRate / 12

minimum = balance / 12
maximum = (balance * (1 + monthlyInterestRate)**12) / 12.0

guessMinimum = (minimum + maximum)/2

remain = balance #if you payed nothin, the remain is the balance!!!!

precision = 0.10  #you choose....

while (remain >= precision):

    guessMinimum = (minimum + maximum)/2


    for i in range (1,13):

        newBalance = remain - guessMinimum
        monthInterest = annualInterestRate/12*newBalance
        remain = newBalance+monthInterest

    # after one month, the CODE need to check about the remain

    if (remain < 0): #paying too much.... need to decrease the value

        maximum = guessMinimum      #remember my beautiful draw above!!
        remain = balance  # reset the remain to start again!!

    elif (remain > precision): #paying less .... need to increase the value
        minimum = guessMinimum
        remain = balance  # reset the remain to start again!!   

print "Lowest Payment: %.2f" %(guessMinimum)

That's it.

Answer 2

I think this solution should work,

balance = 999999
annualInterestRate = 0.18

monthlyInterestRate = annualInterestRate / 12
lowerBound = balance / 12
upperBound = (balance * (1 + annualInterestRate / 12) ** 12) / 12
originalBalance = balance
lowestBalance = 0.01 # Error margin e.g. $0.01

# Keep testing new payment values until the balance is +/- lowestBalance
while abs(balance) > lowestBalance:
    # Reset the value of balance to its original value
    balance = originalBalance
    # Calculate a new monthly payment value from the bounds
    payment = (upperBound - lowerBound) / 2 + lowerBound

    # Test if this payment value is sufficient to pay off the entire balance in 12 months
    for month in range(12):
        balance -= payment
        balance *= 1 + monthlyInterestRate

    # Reset bounds based on the final value of balance
    if balance > 0:
        # If the balance is too big, need higher payment so we increase the lower bound
        lowerBound = payment
    else:
        # If the balance is too small, we need a lower payment, so we decrease the upper bound
        upperBound = payment

# When the while loop terminates, we know we have our answer!
print "Lowest Payment:", round(payment, 2)

Answer 3

To figure out bugs like this, a good way is just to add some print, for example, I added the following to your code:

print(balance, lo, hi, guess)

Then see what happens, and you can figure out what's going on. As it turns out:

hi = (balance*(1+monthlyInterestRate**12))/12

calculates an upper bound which is too low. Perhaps you meant:

hi = (balance*(1+monthlyInterestRate*12))/12

Answer 4

I changed your code to this:

balance = 999999
annualInterestRate = .18
monthlyInterestRate = annualInterestRate / 12

balanceCOPY = balance

#Bisection search parameters

low = balance / 12
high = (balance * (1 + monthlyInterestRate ** 12)) / 12
epsilon = .01

print "starting high and low guesses"
print "high: %s" % high
print "Low: %s" % low
print "\n"

guess = (low + high) / 2

for i in range(5):

    print "Type of balance: %s" % type(balance)
    print "Balance is: %s" % balance
    print "Low: %s" % low
    print "High: %s" % high
    print "Guess: %s" % guess

    print "monthly interest %s" % (monthlyInterestRate * balance)

    for month in range(1, 13):
        balance -= guess
        balance += monthlyInterestRate * balance

    print "balance after %s" % balance

    if balance > 0 and balance > epsilon:
        print "Change low"
        low = guess
        balance = balanceCOPY
    elif balance < 0 and balance > -epsilon:
        high = guess
        balance = balanceCOPY
    else:
        print('Lowest payment: ', str(round(guess, 2)))
        break

    guess = (low + high) / 2

    print "\n"

A couple of notes: I changed "hi" and "lo" to "high" and "low". It's better to not truncate variable names, since truncated variable names are less readable.

I added debug statements showing the values of various variables.

Here was the result of running the above:

starting high and low guesses
high: 83333.25
Low: 83333


Type of balance: <type 'int'>
Balance is: 999999
Low: 83333
High: 83333.25
Guess: 83333.125
monthly interest 14999.985
balance after 92550.599997
Change low


Type of balance: <type 'int'>
Balance is: 999999
Low: 83333.125
High: 83333.25
Guess: 83333.1875
monthly interest 14999.985
balance after 92549.7726951
Change low


Type of balance: <type 'int'>
Balance is: 999999
Low: 83333.1875
High: 83333.25
Guess: 83333.21875
monthly interest 14999.985
balance after 92549.3590442
Change low


Type of balance: <type 'int'>
Balance is: 999999
Low: 83333.21875
High: 83333.25
Guess: 83333.234375
monthly interest 14999.985
balance after 92549.1522187
Change low


Type of balance: <type 'int'>
Balance is: 999999
Low: 83333.234375
High: 83333.25
Guess: 83333.2421875
monthly interest 14999.985
balance after 92549.048806
Change low

From this you can see that your low value is converging to your high value. In other words, your initial high value isn't high enough. Once they are they same value, the loop will never change anything and will continue forever.

I think this line:

elif balance < 0 and balance < -epsilon:

should read:

elif balance < 0 and balance > -epsilon:

since I think you want balance between 0 and -epsilon rather than less than -epsilon

Also, as @WinstonEwert noted:

hi = (balance*(1+monthlyInterestRate**12))/12 

should be

hi = (balance*(1+monthlyInterestRate)**12)/12 

Answer 5

Here is what I came up with that works. I typically will write functions for these type of things so it can be re-used, even when I don't have to because it gets me in the habit of doing it, and gives me some extra practice with them.

balance = 320000
annualInterestRate=0.2
monthlyIntRate= annualInterestRate/12.0
getpayment=True
ranonce=False
MoMin = balance/12
MoMax = (balance*(1+monthlyIntRate)**12)/12.0
MoPayment = (MoMin+MoMax)/2
NewBal=0

#Create a function to run 12 months of payments, and then create a loop to re-run the function if the Ending Balance is not close enough to 0.
def CCPayment(balance, monthlyIntRate, MoPay):
    global NewBal    
    Month = 1 #Month begins at 1

    while Month <= 12:
            balance = (balance - MoPay)
            balance = balance + (monthlyIntRate * balance)
            NewBal=balance #sets the var NewBal to be used globally
            Month += 1
    if (balance < .02) and (balance > -0.02) : #cannot evaluate to '0' as you are evaluating a float and it will 'inf loop'. Must evaluate it to a number 'close enough'
        return MoPayment
    else:
        return False

while getpayment==True: 
    if CCPayment(balance, monthlyIntRate, MoPayment):
        getpayment=False
        print "Lowest Payment: ", round(CCPayment(balance, monthlyIntRate, MoPayment),2)
    else:
        if NewBal < 0.01: #paid too much! Lower the max payment and rerun function
            if ranonce == True: #Bool check to avoid resetting the Min/Max values before running it once
                MoMax=MoPayment #sets the Max payment to the current monthly payment
                MoPayment=(MoMin+MoMax)/2 #sets the Monthly payment to average the Min/Max payments
            ranonce = True
            CCPayment(balance, monthlyIntRate, MoPayment)

        elif NewBal > 0.01: #didn't pay enough! Raise min payment and rerun function
            if ranonce == True: #Bool check to avoid resetting the Min/Max values before running it once
                    MoMin=MoPayment #sets the Min payment to the current monthly payment
                    MoPayment=(MoMin+MoMax)/2 #sets the Monthly payment to average the Min/Max payments
            ranonce = True
            CCPayment(balance, monthlyIntRate, MoPayment)