Coding challenges on searching smarter: bisection search, logarithmic time, and newton-raphson — MIT problem set

Write the body of lowest_rate_of_return(initial_deposit), MIT's Part C program: use bisection search to find the lowest rate of return r that grows an initial deposit into the down payment on a house in 3 years.

In Part A and B, you explored how (1) the percentage of your salary saved each month and (2) a semi-annual raise affects how long it takes to save for a down payment given a fixed rate of return, r.

In Part C, we will have a fixed initial amount and the ability to choose a value for the rate of return, r. Given an initial deposit amount, our goal is to find the lowest rate of return that enables us to save enough money for the down payment in 3 years.

User Inputs. MIT's program reads one value with input() and casts it as a float: the initial amount in your savings account (initial_deposit). Here the parameter initial_deposit stands in for that input() call. It already holds the number the user would have typed, so use it exactly as you would have used the value input() returned. Write your program under MIT's two comment headers in the starter and keep the last line, return r, steps, which hands your two output variables to the tests.

Writing the Program. Write a program to calculate the minimum rate of return r needed in order to reach your goal of a sufficient down payment in 3 years, given an initial_deposit. To simplify things, assume:

1. The cost of the house that you are saving for is $800,000.
2. The down payment is 25% of the cost of the house.

Use the following formula for compound interest in order to calculate the predicted savings amount given a rate of return r, an initial_deposit, and months:

amount_saved = initial_deposit * (1 + r / 12) ** months

You will use bisection search to determine the lowest rate of return r that is needed to achieve a down payment on a $800,000 house in 36 months. Since hitting this exact amount is a bit of a challenge, we only require that your savings be within $100 of the required down payment. For example, if the down payment is $1000, the total amount saved should be between $900 and $1100 (exclusive).

Your bisection search should update the value of r until it represents the lowest rate of return that allows you to save enough for the down payment in 3 years. r should be a float (e.g. 0.0704 for 7.04%). Assume that r lies somewhere between 0% and 100% (inclusive).

Outputs.

1. The variable steps should reflect the number of steps your bisection search took to get the best r value (i.e. steps should equal the number of times that you bisect the testing interval).
2. The variable r should be the lowest rate of return that allows you to save enough for the down payment in 3 years.

Notes

• There may be multiple rates of return that yield a savings amount that is within $100 of the required down payment on a $800,000 house. The grader will accept any of these values of r.
• If the initial deposit amount is greater than or equal to the required down payment minus $100, then the best savings rate is 0.0.
• If it is not possible to save within $100 of the required down payment in 3 years given the initial deposit and a rate of return between 0% and 100%, r should be assigned the value None. Note: the value None is different than "None". The former is Python's version of a null value, and the latter is a string.
• Depending on your stopping condition and how you compute the amount saved for your bisection search, your number of steps may vary slightly from the example test cases. Running the tests should give you a good indication of whether or not your number of steps is close enough to the expected solution.
• If a test is taking a long time, you might have an infinite loop! Check your stopping condition.

Testing. MIT's three manual test cases, as calls to your function. MIT's program prints Best savings rate: and Steps in bisection search:; your function returns the pair r, steps instead.

print(lowest_rate_of_return(65000))  # (0.380615234375, 12)
print(lowest_rate_of_return(150000))  # (0.09619140625, 11)
print(lowest_rate_of_return(1000))  # (None, 0)

As MIT notes, your best savings rate may be very close to these numbers rather than equal to them, and your number of steps may vary with how you implemented your bisection search. The tests accept any r whose savings land within $100 of the down payment and a step count within 2 of MIT's, except MIT's own tester case of an initial deposit of 187401, which must take exactly 12 steps. Neither special case (0.0 or None) checks the number of steps.

Adapted for the browser: MIT's ps1c.py script is wrapped in the function lowest_rate_of_return(initial_deposit), as MIT's own put_in_function.py does, so the parameter replaces the input() call and the function returns r, steps instead of printing them.