What is wrong with my bisection algorithm?

Question

My homework problem: Find the smallest monthly payment required pay off a given loan principal within a year. One-twelfth of the original balance is a good lower bound; a good upper bound is one-twelfth of the balance, after having its interest compounded monthly for an entire year.

In short:

Monthly interest rate = (Annual interest rate) / 12.0
Monthly payment lower bound = Balance / 12
Monthly payment upper bound = (Balance * (1 + Monthly interest rate)**12) / 12.0

I have to write a bisection search to find that smallest monthly payment to the cent.

Every time I run this code I get the lowest payment to be a value a couple hundred off from the correct solution.

balance = 414866
annualInterestRate = 0.22
month = 0
monthlyinterest = (annualInterestRate) / 12.0
updatedbalance = balance
monlowbound = balance / 12
monupbound = (balance * (1 + monthlyinterest)**12) / 12.0
mid = (monlowbound + monupbound) /2
minpay = 0

while balance > 0 and month <= 12:
    balance = updatedbalance
    updatedbalance = ((monthlyinterest * balance) + balance) - minpay
    month += 1
    if updatedbalance > 0:
        minpay = (mid + monupbound)/2
        mid = monlowbound
    if updatedbalance < 0:
        minpay = (monlowbound + mid)/2
        monupbound = mid
    else:
        print("Lowest payment:" + " " + str(round(minpay,2)))

This is what I get as the output:

Lowest payment: 40888.41
Lowest payment: 38783.0
Lowest payment: 38783.0
Lowest payment: 38783.0
Lowest payment: 38783.0
Lowest payment: 38783.0
Lowest payment: 38783.0
Lowest payment: 38783.0
Lowest payment: 38783.0
Lowest payment: 38783.0
Lowest payment: 38783.0
Lowest payment: 38783.0
Lowest payment: 38783.0

Is there a reason you're not just directly finding the value with algebra? — E.D.
– E.D., Commented Jun 12, 2017 at 20:57
Unless annualInterestRate doesn't actually mean what it's named to mean, you're calculating monthly interest rate incorrectly. Use the equality balance*(1+annualInterestRate) == balance*(1+monthlyInterestRate)^12 to calculate monthly interest rate. — E.D.
– E.D., Commented Jun 12, 2017 at 21:02
Since you have a resolution, please remember to up-vote useful items and choose a best answer. That allows Stack Overflow to properly archive teh question. — Prune
– Prune, Commented Jun 12, 2017 at 21:55
@ErikBrodyDreyer: The programming problem is to implement a binary search. Direct computation nullifies the exercise. Also, I'm not sure what your "equality" calculation is trying to do; I don't think your algebra does what you intended. — Prune
– Prune, Commented Jun 12, 2017 at 21:59

Prune · Accepted Answer · 2017-06-12 21:24:29Z

1

The major problem is that you apply your feedback adjustment logic (adjusting the monthly payment) every month. You need to wait until the end of the year, and then adjust the payment. All of that should be wrapped inside a while loop that continues until you get "close enough" ... say, within a full penny of the previous payment. Something like this:

last_pay = -1000   # Ridiculous value to start the process

while abs(last_pay - minpay) > 0.01:
    # use your current logic for paying off one year, including
    ...
    for month in range(12):
        ....

    # HERE is where you check the final balance 
    #   to see whether you're high or low.
    # Then adjust your monthly payment (minpay)

Does this get you going?

answered Jun 12, 2017 at 21:24

Prune

78k14 gold badges63 silver badges83 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

WNG · Accepted Answer · 2017-06-12 21:34:29Z

Your algorithm does not work.

What you want is :

A function f that gives you the final balance for any fixed payment
An algorithm to find the root of this function, i.e. the monthly fixed payment that needs to be paid for the final balance to be as close as zero as possible. With a given f function, a recursive approach would be something like :

You seem to be doing both at the same time, i.e. you change your "mid" value while you're still computing. I suggest you write down your algorithm before you try to code it to realize the flow you probably want :

def finalbalance(fixedpayment): #code that determines the balance status

def solvebisection(lowbound,highbound,function=finalbalance,tofind=0): #Recursive coding to "find the root"

Collectives™ on Stack Overflow

What is wrong with my bisection algorithm?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related