Question

I am having difficulty with 6.00SC (2011) Problem Set 1 Problem 3 (using bisection search to determine how much to pay a balance).

I understand the bisection part well enough, but do not fully get where epsilon comes into it... I understand that it is used to determine the accuracy of values, but I can't seem to figure out how to combine the bisection and epsilon concepts.

I am using several loops and if statements for my solution, but am not having any success.

Any advice on this problem would be most welcome. Thanks in advance!

Answer 1

Epsilon is the space in which the range of search is divided.

Answer 2

This is what i understood, if your goal is to rich a value of for example 1.5, and your epsilon is 0.1 if the bisection finds the value of 1.6 it will stop. In a way the your epsilon sets the space in which the range of search is divided. But maybe im wrong because, i had trouble understanding the function of the epsilon, in the case of the bisection search. Sorry for my poor english

Answer 3

Thanks Tom. I've actually gotten to the point where I have looked at the professor's solution, which I don't seem to understand either :(

Why is he running through the following loop after calculating the updated balance for a year?
if (high_payment - low_payment < 0.005):
only to then go ahead and calculate the balance a second time?
Why does the difference in upper and lower bounds matter? Don't we care that the payment didn't pay off the balance in 12 months?

Answer 4

balance=float(input('Enter the outstanding balance on your credit card:'))
yrate=float(input('Enter the annual credit card interest rate as a decimal:'))
intpaid=balance*(yrate/12)
inibalance=balance
low=0
high=balance+intpaid

while (high-low)>0.005:
balance=inibalance
mpayment=(low+high)/2.0
for i in range (1,13):
intpaid=balance*(yrate/12)
ppaid=mpayment-intpaid
balance=balance-ppaid
if balance <= 0:
break
if balance>0:
low=mpayment

else :
high=mpayment


print ('Monthly payment to pay off debt in 1 year:',round (mpayment,2))
print('Number of months needed:',i)
print ('Balance',round(balance,2))


Try to understand this solution, I think it's simpler... if you have doubts tell

Answer 5

what does it mean that the high and low are only .005 dollars(?) apart - it's possible that that is a stop-gap measure to prevent a long or infinite recursion/iteration.

epsilon:
all numbers cannot be accurately represented as a floating point number. if you are making decsions based the result of floating point calcs you should use a tolerance to account for these 'floating point errors'.
also if there is an acceptable error for your calculation results, you can reduce the resources it takes to find the answerby incorporating a tolerance.

Answer 6

Don't forget to post your code to one of these:

http://dpaste.com/
http://pastebin.com/
http://gist.github.com/

Put your code up and paste a link. Then people can see and more easily debug it.

Answer 7

@bwCA "what does it mean that the high and low are only .005 dollars(?) apart - it's possible that that is a stop-gap measure to prevent a long or infinite recursion/iteration."

It has nothing to do with possibility... it has to do with the regular occurrence of.

The problem deals with floating point math. In fractions it is easy to say 2/3 - 1/3 = 1/3. But if I say, "Now do it in decimals to 8 digits after the decimal," you do .66666667 - .33333333 = .33333334 and suddenly it is not exactly 1/3. The same problem happens all the time in floating point math.

The whole goal of Epsilon \(\epsilon\) is to give you a point where it is so close to paid off that you accept that it is paid off. In the above example, half a cent. If the floating point error is less than half a cent left over, call it done.

Answer 8

I used much of the code from the second problem, and found this to be very close to the homework answer without belaboring the problem too much:

balance = float(raw_input("Please enter your outstanding balance:"))
annual_rate = float(raw_input("Please enter your annual interest rate as a decimal:"))

low = balance/12
high = (balance*(1+(annual_rate/12))**12)/12
midpoint = (low + high)/2



monthly_rate = annual_rate/12
compounded_interest = annual_rate*balance
remaining_balance = balance



while high - low > 0.0001:
month =0
remaining_balance = balance
monthlypayment=midpoint

while month < 12 and remaining_balance > 0:
month += 1

# calculate interest for the month
interest = monthly_rate * remaining_balance

#calculate remaining principal
remaining_balance -= monthlypayment

#calculate principal plus interest
remaining_balance +=interest


if remaining_balance > 0:
low = midpoint
midpoint = (low+high)/2

else:
high = midpoint
midpoint = (low+high)/2


#print monthlypayment
#print interest
#print remaining_balance
#print month



print "RESULT"
print "Monthly payment to pay off debt in 1 year: $", round(monthlypayment,2)
print "Number of months needed: ", month
print "Balance: $", round(remaining_balance,2)

Answer 9

Thank you for all of the replies!

what is the point of "while high - low > 0.0001:" in the example above (but also in the posted solution file)? Why are we checking the difference between the upper and lower bounds?

Answer 10

@anarpis
This is how I used epsilon to solve the problem.

```
def cc_payments_max(balance,ir,max_payment):
for i in range(1,13):
interest_paid = (ir/12.0*balance)
principle_paid = max_payment-interest_paid
balance = balance-principle_paid
return balance,i

def bisection_search(balance,ir):
epsilon = .01
lower_bound = balance/12.0
upper_bound = (balance*(1.0+(ir/12.0))**12.0)/12.0
guess = (upper_bound+lower_bound)/2
guesses = 0
while abs(round(cc_payments_max(balance,ir,guess)[0],2)) > epsilon:
if cc_payments_max(balance,ir,guess)[0] > 0:
lower_bound = guess
guess = (upper_bound+lower_bound)/2
guesses+=1
elif cc_payments_max(balance,ir,guess)[0] < 0:
upper_bound = guess
guess = (upper_bound+lower_bound)/2
guesses+=1
else:
print("There is a problem!")
return
return round(guess,2), guesses
print bisection_search(320000.0,.2)
```