You'll notice that in Problem 2, your monthly payment had to be a multiple of $10. Why did we make it that way? You can try running your code locally so that the payment can be any dollar and cent amount (in other words, the monthly payment is a multiple of $0.01). Does your code still work? It should, but you may notice that your code runs more slowly, especially in cases with very large balances and interest rates. (Note: when your code is running on our servers, there are limits on the amount of computing time each submission is allowed, so your observations from running this experiment on the grading system might be limited to an error message complaining about too much time taken.)

Well then, how can we calculate a more accurate fixed monthly payment than we did in Problem 2 without running into the problem of slow code? We can make this program run faster using a technique introduced in lecture - bisection search!

The following variables contain values as described below:

balance - the outstanding balance on the credit card

annualInterestRate - annual interest rate as a decimal

To recap the problem: we are searching for the smallest monthly payment such that we can pay off the entire balance within a year. What is a reasonable lower bound for this payment value? $0 is the obvious anwer, but you can do better than that. If there was no interest, the debt can be paid off by monthly payments of one-twelfth of the original balance, so we must pay at least this much every month. One-twelfth of the original balance is a good lower bound.

What is a good upper bound? Imagine that instead of paying monthly, we paid off the entire balance at the end of the year. What we ultimately pay must be greater than what we would've paid in monthly installments, because the interest was compounded on the balance we didn't pay off each month. So a good upper bound for the monthly payment would be 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 x (1 + Monthly interest rate)12) / 12.0

Write a program that uses these bounds and bisection search (for more info check out the Wikipedia page on bisection search) to find the smallest monthly payment to the cent (no more multiples of $10) such that we can pay off the debt within a year. Try it out with large inputs, and notice how fast it is (try the same large inputs in your solution to Problem 2 to compare!). Produce the same return value as you did in Problem 2.

Note that if you do not use bisection search, your code will not run - your code only has 30 seconds to run on our servers.

Test Cases to Test Your Code With. Be sure to test these on your own machine - and that you get the same output! - before running your code on this webpage!
Click to See Problem 3 Test Cases

The code you paste into the following box should not specify the values for the variables balance or annualInterestRate - our test code will define those values before testing your submission.

i = 1 +(annualInterestRate/12)

term = 1
sum = 0
for m in range(0,12):
sum += term
term = term/i
x = balance/sum
print("Lowest Payment: "),round(x,2)

To solve this problem, we can use the bisection search algorithm. Bisection search is an efficient searching algorithm that can find a solution within a specified range by repeatedly dividing the range in half and checking if the solution is within the lower or upper half.

In this case, we want to find the smallest monthly payment that will pay off the debt within a year. We can use the following steps to implement the bisection search algorithm:

1. Compute the monthly interest rate by dividing the annual interest rate by 12.
2. Compute the lower bound for the monthly payment by dividing the balance by 12.
3. Compute the upper bound for the monthly payment by multiplying the balance by the compound interest rate (1 + monthly interest rate)^12, and then dividing by 12.
4. Initialize the guess for the monthly payment as the average of the lower and upper bounds.
5. Repeat the following steps until the monthly payment is within a small tolerance:
a. Set the balance to the original balance.
b. For each month in a year, subtract the monthly payment from the balance and add the monthly interest to the balance.
c. Update the lower or upper bound based on whether the guess is too high or too low.
d. Update the guess as the average of the new lower and upper bounds.
6. When the monthly payment is within the tolerance, return the guess as the smallest monthly payment.

Here's an example implementation in Python:

```python
# Define the function to calculate the smallest monthly payment
def calculate_smallest_payment(balance, annualInterestRate):
# Set the tolerance for the solution
epsilon = 0.01

# Compute the monthly interest rate
monthlyInterestRate = annualInterestRate / 12.0

# Compute the lower and upper bounds for the monthly payment
lowerBound = balance / 12.0
upperBound = (balance * (1 + monthlyInterestRate)**12) / 12.0

# Initialize the guess for the monthly payment
guess = (lowerBound + upperBound) / 2

# Start the bisection search
while True:
# Set the balance to the original balance
updatedBalance = balance

# Compute the balance for each month using the guess for the monthly payment
for month in range(12):
monthlyUnpaidBalance = updatedBalance - guess
updatedBalance = monthlyUnpaidBalance + monthlyInterestRate * monthlyUnpaidBalance

# Check if the balance is within the tolerance
if abs(updatedBalance) < epsilon:
return round(guess, 2) # Return the smallest monthly payment

# Update the lower or upper bound based on the guess
if updatedBalance < 0:
upperBound = guess
else:
lowerBound = guess

# Update the guess
guess = (lowerBound + upperBound) / 2

# Define the balance and annual interest rate (already provided in the exercise)
balance = 320000
annualInterestRate = 0.2

# Call the function to calculate the smallest monthly payment
smallestPayment = calculate_smallest_payment(balance, annualInterestRate)

# Print the result
print("Lowest Payment:", smallestPayment)
```

You can run this code locally to find the smallest monthly payment for the given `balance` and `annualInterestRate`. Be sure to test it with different inputs and compare the results with the previous solution from Problem 2. Note that this solution will be faster for large inputs compared to the previous solution because it uses the bisection search algorithm.