While going through the third part of a problem from one of MIT's OCW Problem sets, I encountered some doubts. The problem description is as follows:

Part C: Finding the right amount to save away:

In Part B, you had a chance to explore how both the percentage of your salary that you save each month and your annual raise affect how long it takes you to save for a down payment. This is nice, but suppose you want to set a particular goal, e.g. to be able to afford the down payment in three years. How much should you save each month to achieve this? In this problem, you are going to write a program to answer that question. To simplify things, assume: 3

1. Your semiannual raise is .07 (7%)
2. Your investments have an annual return of 0.04 (4%)
3. The down payment is 0.25 (25%) of the cost of the house
4. The cost of the house that you are saving for is $1M.

You are now going to try to find the best rate of savings to achieve a down payment on a $1M house in 36 months. Since hitting this exactly is a challenge, we simply want your savings to be within $100 of the required down payment. In ps1c.py , write a program to calculate the best savings rate, as a function of your starting salary. You should use bisection search to help you do this efficiently. You should keep track of the number of steps it takes your bisections search to finish. You should be able to reuse some of the code you wrote for part B in this problem. Because we are searching for a value that is in principle a float, we are going to limit ourselves to two decimals of accuracy (i.e., we may want to save at 7.04% or 0.0704 in decimal – but we are not going to worry about the difference between 7.041% and 7.039%). This means we can search for an integer between 0 and 10000 (using integer division), and then convert it to a decimal percentage (using float division) to use when we are calculating the current_savings after 36 months. By using this range, there are only a finite number of numbers that we are searching over, as opposed to the infinite number of decimals between 0 and 1. This range will help prevent infinite loops. The reason we use 0 to 10000 is to account for two additional decimal places in the range 0% to 100%. Your code should print out a decimal (e.g., 0.0704 for 7.04%).

The problem description clearly states later on that this problem may be solved in various different ways by implementing bisection search in different styles, which would ultimately give different results and they are all correct, i.e., there are multiple rates that will allow for the savings to be in ~100 of the downpayment. However, the solution to the problem is no longer my concern, as I realize I already solved it; what I want to know now is what modifications do I have to make to my code so I can produce outputs with similar accuracy to that of the expected test output provided below:

Test Case 1

>>> Enter the starting salary: 150000
Best savings rate: 0.4411
Steps in bisection search: 12

This is my solution to the problem:

def calc_savings(startingSalary:int, nummonths:int, portion:float):
    """
    Calculated total savings with fixed annual raise and r.o.i for x no. of months 
    at 'portion' percentage of salary saved every month.
    """
    savings = 0
    salary=startingSalary
    for months in range(1, nummonths 1):
        savings = (salary/12*portion) (savings*(0.04/12))
        if months%6==0:
            salary = salary (0.07*salary)

    return savings

cost = 1_000_000
downpayment = cost*0.25
startingsalary = int(input("Enter starting salary: "))
step = 0
high = 10000
low = 0

if startingsalary*3 < downpayment:
    print("Saving the down payment in 36 months with this salary is not possible.")

else:
    while True:
        portion = int((high low)/2)/10000
        current_savings=calc_savings(startingsalary, 36, portion)

        if downpayment - current_savings < 100 and downpayment-current_savings>=0:
            break
        elif downpayment-current_savings>=100:
            low = portion*10000
            step =1
        elif downpayment-current_savings < 0:
            high = portion*10000
            step =1
    print(f"Best savings rate: {portion}")
    print(f"Steps in bisection search: {step}")

And this is the result I'm getting:

>>> Enter the starting salary: 150000
Best savings rate: 0.441
Steps in bisection search: 12

I realized that this has something to do with the way I choose my limits for the bisection search and how I later convert the result I get from it back to the required number of significant digits.

After playing around with the code for some time, I realized that the no. of significant digits in my result is the same as the expected results, I tested this by changing the no. of months to 40 from 36 and figured that it says 0.441 because it's actually 0.4410 which is super close to 0.4411.

I'm just wondering if there's anything I can do to my code to hit that exact 0.4411.

CodePudding user response：

First, you are not doing floating point optimization. Even though you use floating point operations for intermediate steps, you are saving your optimization variable in a fixed-point format, therefore doing fixed point optimization. When you use an integer and a constant scaling factor (100000) to represent a rational or real number that is fixed point, not floating point.

Since you are working with a fixed point value, if you want to be sure of getting a result that's accurate to the nearest .0001, you simply have to change your exit condition. Instead of exiting as soon as your answer is correct to the nearest $100 in terms of dollars saved, wait until the answer is correct to the nearest .0001 as a fraction of the salary. Which, because of your fixed point representation means waiting until high and low are separated by 1 count, and then reporting whichever of the numbers gives the closest result to the desired final savings.

Side note: Since high and low are always integers, you can use (high low)//2 to use integer operations to get the same result as int((high low)/2) without converting to floats and back again.