Bisection… Insert algorithm

I’ve been a bit distracted lately.

I didn’t accomplish much in the way of studying this weekend due to my National Guard commitments. Coupled with that is the fact that I’ve hit a bit of the lecture / code that stumps(ed) me a bit. I have this really interesting mindset that wont allow me to go on unless I actually understand 100% what is happening. I’ll obsess over a particular bit of logic until I find the answer.

The problem set I’ve been toiling over is three part:

1) I had to write a program that computed what would happen if we only paid the minimum amount on our credit card debt. The problem I encountered here was that I didn’t know the ” += ” and ” -= ” operators. I couldn’t figure out how to take a new value for a variable and have that value carried through the next loop. So those operators solved that and gave me a wee high.

2) This problem called for what it took to pay off my credit card in one year. I really had to learn how to implement loops in order to find a value that met the requirements. The problem I had here was that my answers never equaled the instructor’s examples. I wracked my brains on this until this weekend when I had the chance to sit and chat with a few soldiers in my unit with coding experience.

We compared my program with the instructors and tried to work out the logic gaps in mine. I started copying over different variables and then my program worked. I couldn’t figure out the “why” though. Then one of my sargents suggested having it Print back to me the value of that particular variable each time it looped. Long story short, that simple trick helped me recognize what was happening in the program as far as its logic is concerned.

+ 10 coding experience gained —- 3,046 needed to level up.

3) Now for the wall. Bisection search is a bit of a bear for me. I understand the idea behind it. Its rather simple. However, implement it has been a bit confusing. Especially the algorithm. I posted a question on OpenStudy for the course and somebody explained the math behind it. However I’m left wondering if I should have known the formula already or I should have just taken the prof at his word (it was provided in the problem set).

So being stuck on understanding HOW to do this at all I took at look at the instructors answers (not something I’m want to do). For reference, here is what he provided:

# 6.00 PS1-C Solution
# Uses bisection search to find the fixed minimum monthly payment needed
# to finish paying off credit card debt within a year

# Retrieve input
original_balance = float(raw_input("Enter the outstanding balance on your credit card: "))
interest_rate = float(raw_input("Enter the annual credit card interest rate as a decimal: "))

# Initialize state variables
balance = original_balance
low_payment = balance/12
high_payment = (balance*(1+(interest_rate/12))**12)/12

# Use bisection search until the search space is sufficiently small
while True:
    balance = original_balance
    monthly_payment = (low_payment + high_payment)/2

    # Simulate passage of time until outstanding balance is paid off
    # Each iteration represents 1 month
    for month in range(1,13):
        interest = round(balance*interest_rate/12, 2)
        balance += interest - monthly_payment
        if balance <= 0:
    if (high_payment - low_payment < 0.005):
        # Bisection search space is small enough
        # Print result
        print "RESULT"

        # Round monthly payment up to the nearest cent
        monthly_payment = round(monthly_payment + 0.004999, 2)
        print "Monthly payment to pay off debt in 1 year:", round(monthly_payment,2)

        # Recompute remaining balance and the number of months needed
        balance = original_balance
        for month in range(1,13):
            interest = round(balance*interest_rate/12, 2)
            balance += interest - monthly_payment
            if balance <= 0:
        print "Number of months needed:", month
        print "Balance:", round(balance,2)
    elif balance < 0:
        #Paying too much
        high_payment = monthly_payment
        #Paying too little
        low_payment = monthly_payment

The biggest thing I don’t get is why it recomputes the balance and the number of months needed when it was done earlier in the script. Needless to say, this one is causing me a bit of a brain jam.

I think this is one I’ll actually have to sit down with Jedi Dave and discuss here in the future. In the mean time, I’m going to put it in my “to-solve-later-and-use-to-take-over-the-world” folder.

Time to watch part of a lecture before bed. Onward!


2 thoughts on “Bisection… Insert algorithm

  1. You’re overthinking it. All the re-computing does is verifies that the monthly payment computed previously will actually do the job of paying off the debt. I don’t see that as part of the problem as stated, but I guess they want to be sure that rounding errors don’t throw you off the 12-month goal.

  2. Regarding the maths behind this algorithm, it looks really similar to Newton’s method for deriving the roots of a function, If you’ve had a calculus class, you might recall that. If you haven’t had a calculus class…
    “You will go to the Dagobah system….”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s