[Tutor] Python problem
Vakhtang Kvaratskhelia
va_kvaratskhelia at cu.edu.ge
Sat Feb 27 02:23:19 EST 2021
Thank you very much for the reply.
i worked out other small problems but the main question was: can i use
bisection search with the integer division?
Every time i run a bisection search code through python tutor
visualization the outcome is the same: the integer division turns into an
infinite loop.
What i mean is that if i write the code (for simplicity i have
precalculated variables mentioned in the previous emails and narrowed the
code down to the following ) :
low=0
high=10000
epsilon=100
portion_saved=0
while abs(250,000 - portion_saved * 566,774) >= epsilon:
if portion_saved * 566774 < 250,000 :
low=portion_saved
else:
high=portion_saved
portion_saved=(high+low) / 2
print(portion_saved)
The result is the same as the answer in the book that had the problem.
but if i run the code:
low=0
high=10000
epsilon=100
portion_saved=0
while abs(250,000 - portion_saved * 566,774) >= epsilon:
if portion_saved * 566,774 < 250,000 :
low=portion_saved
else:
high=portion_saved
portion_saved=(high+low) // 2
print(portion_saved)
Where i use "//" instead of "/" i get infinite loop because the "//" gets
stuck on one particular guess and doesn't continue the search as the "/"
division would.
So then how do i use the hint which was given to me in the book? the hint
was the following:
"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%)."
Is it possible that the hint doesn't mean "//" by the "integer division"?
Thank you in advance.
On Tue, Feb 23, 2021 at 10:42 PM Dennis Lee Bieber <wlfraed at ix.netcom.com>
wrote:
> On Sat, 20 Feb 2021 15:27:01 +0400, Vakhtang Kvaratskhelia
> <va_kvaratskhelia at cu.edu.ge> declaimed the following:
>
> I'm going all the way back to your first post just to comment on a
> number of inefficiencies seen in the provide code.
>
> Note: as you have NOT provided the code using // I can not comment
> on
> possible problems there...
>
> >
> >However i am unable to prevent an infinite loop in case the annual salary
> >is 10,000
> >
>
> Given the nature of the values provided in the code, I don't know
> if
> you posted scaled integers (for use in the // case?) or "real" values. I
> would suspect that "annual salary" that low is a value that will not
> converge to a solution -- that is, the income is too low to make payments
> which will close out the cost in the time span specified.
>
>
> >I want to use this hint : "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 clause would appear to define the convergence/termination
> criteria. It is unclear, however, if that criteria is to be abs(upper -
> lower) < 0.01, or < 0.001, or something else like < 0.005.
>
> Now, comments on your posted code...
>
> >
> >annual_salary=150000
> >total_cost=1000000
> >Months=36
> >semi_annual_raise=0.07
> >portion_down_payment=0.25
> >r=0.04
>
> This is not used in your code -- I'm presuming it was meant to be
> used
> where your hard-coded 0.04 below.
>
> >portion_saved=0
> >epsilon=100
> >possible_savings=0
> >Steps=0
> >for i in range(0,Months):
>
> range(0, months) is the same as range(months)
>
> However, since you keep doing (i+1)%6 in subsequent code, it would
> be
> better to use range(1, months+1) and i%6 which uses
> only one
> addition.
>
> > possible_savings+= annual_salary/12 + possible_savings*0.04/12
>
> Similarly, you keep dividing annual salary by 12, and 0.04 by 12.
> It
> would be more efficient to precompute monthly salary and monthly interest
> rate outside the loop (and recompute monthly salary when a raise is
> applied).
>
> > if (i+1)%6 == 0:
>
> As mentioned, changing the range() call allows removing the +1 from
> this.
>
> > annual_salary=annual_salary*(1+semi_annual_raise)
>
> And here, again, you have an addition that could have been done
> outside
> the loop. My solution keeps an addition, but changes where it takes place.
>
> >low=0
> >high=10000
> >while abs(total_cost*portion_down_payment - portion_saved *
> >possible_savings) >= epsilon:
>
> Again, total cost * portion down payment never changes, precompute
> it
> outside the loop.
>
> I also note that "high" appears to be a scaled integer percentage,
> yet
> this code is not using the // operator. Low/high should be decimal fraction
> percentage 0.0/1.0. As noted above, your convergence criteria is supposed
> to be when the difference between low/high is < some limit. I don't
> understand what your "while" statement is doing with some epsilon
> (especially as I don't know if your "100" epsilon is supposed to represent
> actual 100.0, or is a scaled integer again and represents 1.0)
>
> > if portion_saved * possible_savings < total_cost*portion_down_payment
> :
> > low=portion_saved
> > else:
> > high=portion_saved
> > portion_saved=(high+low)/2
>
> You never test for convergence -- should low/high end up with the
> same
> value, portion saved will not change.
>
> You also never showed us the result of running your code, so
> knowing
> what is a "right" result is difficult. My attempt at rewriting your logic
> into a reusable format (your code requires editing to change any parameter)
> resulted in... (watch out for line wraps)
>
> -=-=-
>
> def getInt(prompt):
> while True:
> sInt = input("Enter %s as an integer: " % prompt)
> try:
> iInt = int(sInt)
> break
> except: #yes, a bare except clause, this is not production
> print("Invalid entry for integer: '%s'\n" % sInt)
> return iInt
>
> def getFloat(prompt):
> while True:
> sFloat = input("Enter %s as a float: " % prompt)
> try:
> fFloat = float(sFloat)
> break
> except: #yes, a bare except clause, this is not production
> print("Invalid entry for float: '%s'\n" % sFloat)
> return fFloat
>
> def getPercent(prompt):
> while True:
> sFloat = input("Enter %s as a float percentage [nn.n, not 0.nnn]: "
> % prompt)
> try:
> fFloat = float(sFloat)
> if not (0.0 <= fFloat <= 100.0):
> print("Invalid range for percent 0.0 - 100.0: %s\n" %
> fFloat)
> else:
> break
> except: #yes, a bare except clause, this is not production
> print("Invalid entry for float: '%s'\n" % fFloat)
> return fFloat / 100.0 #convert to decimal fraction 0.0-1.0
>
>
> annualSalary = getFloat("annual salary")
> monthlySalary = annualSalary / 12.0 #algorithm works in months
>
> totalCost = getFloat("total cost")
>
> months = getInt("months")
>
> raisePercentRate = getPercent("rate of periodic raises")
> raisePeriod = getInt("months between raises")
>
> downPaymentRate = getPercent("percent of cost used for down payment")
>
> annualInterestRate = getPercent("annual interest rate")
> monthlyInterestRate = annualInterestRate / 12.0
>
> convergenceCriteria = getPercent("convergence criteria")
>
> #compute maximum possible savings
> possibleSavings = 0
> for month in range(1, months + 1):
> possibleSavings += monthlySalary + possibleSavings *
> monthlyInterestRate
> if month % raisePeriod == 0:
> annualSalary += annualSalary * raisePercentRate
> monthlySalary = annualSalary / 12.0
>
> #iterate over percentage (as decimal fraction) range
> steps = 0
> low = 0.0
> high = 1.0
> downPayment = totalCost * downPaymentRate
> while abs(high - low) > convergenceCriteria:
> portionSaved = (high + low) / 2.0
> steps += 1
> if portionSaved * possibleSavings < downPayment:
> low = portionSaved
> else:
> high = portionSaved
>
> print("Optimal portion saved is %7.2f %%" % (portionSaved * 100.0))
> print("Search required %s steps\n\n" % steps)
>
> -=-=-
>
> ... which produced the following when entering what I think is your set of
> parameters. I have no idea if the results are correct.
>
> -=-=-
> C:\Users\Wulfraed\Documents\_Hg-Repositories\Python
> Progs>bisectionSearch.py
> Enter annual salary as a float: 150000.0
> Enter total cost as a float: 1000000.0
> Enter months as an integer: 36
> Enter rate of periodic raises as a float percentage [nn.n, not 0.nnn]: 7.0
> Enter months between raises as an integer: 6
> Enter percent of cost used for down payment as a float percentage [nn.n,
> not 0.nnn]: 25.0
> Enter annual interest rate as a float percentage [nn.n, not 0.nnn]: 4.0
> Enter convergence criteria as a float percentage [nn.n, not 0.nnn]: 1.0
> Optimal portion saved is 44.53 %
> Search required 7 steps
>
>
>
> C:\Users\Wulfraed\Documents\_Hg-Repositories\Python Progs>
> -=-=-
>
> Out of curiosity, just what does "portion saved" really represent?
> In
> my tests it appears to be the percentage of salary required to make
> payments, not the amount one saves.
>
> Also, there is no test for feasibility -- all three of these runs
> came
> with the same result, but that result likely means the salary is too small
> to make the payments.
>
> -=-=-
> C:\Users\Wulfraed\Documents\_Hg-Repositories\Python
> Progs>bisectionSearch.py
> Enter annual salary as a float: 15000.0
> Enter total cost as a float: 1000000.0
> Enter months as an integer: 36
> Enter rate of periodic raises as a float percentage [nn.n, not 0.nnn]: 7.0
> Enter months between raises as an integer: 6
> Enter percent of cost used for down payment as a float percentage [nn.n,
> not 0.nnn]: 25.0
> Enter annual interest rate as a float percentage [nn.n, not 0.nnn]: 4.0
> Enter convergence criteria as a float percentage [nn.n, not 0.nnn]: 1.0
> Optimal portion saved is 99.22 %
> Search required 7 steps
>
>
>
> C:\Users\Wulfraed\Documents\_Hg-Repositories\Python
> Progs>bisectionSearch.py
> Enter annual salary as a float: 10000.0
> Enter total cost as a float: 1000000.0
> Enter months as an integer: 36
> Enter rate of periodic raises as a float percentage [nn.n, not 0.nnn]: 7.
> Enter months between raises as an integer: 6
> Enter percent of cost used for down payment as a float percentage [nn.n,
> not 0.nnn]: 25
> Enter annual interest rate as a float percentage [nn.n, not 0.nnn]: 4
> Enter convergence criteria as a float percentage [nn.n, not 0.nnn]: 1
> Optimal portion saved is 99.22 %
> Search required 7 steps
>
>
>
> C:\Users\Wulfraed\Documents\_Hg-Repositories\Python
> Progs>bisectionSearch.py
> Enter annual salary as a float: 9000
> Enter total cost as a float: 1000000
> Enter months as an integer: 36
> Enter rate of periodic raises as a float percentage [nn.n, not 0.nnn]: 7
> Enter months between raises as an integer: 6
> Enter percent of cost used for down payment as a float percentage [nn.n,
> not 0.nnn]: 25
> Enter annual interest rate as a float percentage [nn.n, not 0.nnn]: 4
> Enter convergence criteria as a float percentage [nn.n, not 0.nnn]: 1
> Optimal portion saved is 99.22 %
> Search required 7 steps
> -=-=-
>
> In fact, annual salary needs to be around 70000.00 before one gets
> something less than "99.22"
>
> -=-=-
> C:\Users\Wulfraed\Documents\_Hg-Repositories\Python
> Progs>bisectionSearch.py
> Enter annual salary as a float: 70000
> Enter total cost as a float: 1000000
> Enter months as an integer: 36
> Enter rate of periodic raises as a float percentage [nn.n, not 0.nnn]: 7
> Enter months between raises as an integer: 6
> Enter percent of cost used for down payment as a float percentage [nn.n,
> not 0.nnn]: 25
> Enter annual interest rate as a float percentage [nn.n, not 0.nnn]: 4
> Enter convergence criteria as a float percentage [nn.n, not 0.nnn]: 1
> Optimal portion saved is 94.53 %
> Search required 7 steps
> -=-=-
>
> A similar condition applies when the annual salary is larger than
> total
> cost.
>
>
> --
> Wulfraed Dennis Lee Bieber AF6VN
> wlfraed at ix.netcom.com
> http://wlfraed.microdiversity.freeddns.org/
>
> _______________________________________________
> Tutor maillist - Tutor at python.org
> To unsubscribe or change subscription options:
> https://mail.python.org/mailman/listinfo/tutor
>
More information about the Tutor
mailing list