[Tutor] Python problem

[dn]

On 23/02/2021 05.47, Vakhtang Kvaratskhelia wrote:
> Thank you very much for the reply.
> 
> I understand those comments, however what i don't understand is how can you
> use integer division "//" with the bisection search code? The "/" division
> works just fine but the "//" doesn't work with the bisection search code.
> 
> Is it possible that the hint is wrong? Or maybe integer division doesn't
> mean "//"


[am assuming you to be a ComSc student studying math/algorithms, and
thus to be held to a different standard to (say) a hobbyist]


The "Is it possible" is easily checked using the documentation and/or
experimentation ("reflection"):

https://docs.python.org/3/library/stdtypes.html#numeric-types-int-float-complex

<<<
x // y floored quotient of x and y...
Also referred to as integer division. The resultant value is a whole
integer, though the result’s type is not necessarily int. The result is
always rounded towards minus infinity: 1//2 is 0, (-1)//2 is -1, 1//(-2)
is -1, and (-1)//(-2) is 0.
>>>

Thus:

>>> 5/2
2.5
>>> 5//2
2
>>> type( 5//2 )
<class 'int'>


>>> 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 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%)."
>>> but i am not able to.

>>         I'm not so certain about that justification for using integers and
>> then
>> converting to float for output... While real world may have an infinite
...


Separate in your mind the two 'values'!

The first is the $value or is it the interest-rate, which is expressed
as a decimal/float.

The second is the list *index* (or "pointer") which *must* be an
integer. [will assume "list" for convenience = any collection]

Back to the docs:

https://docs.python.org/3/reference/expressions.html#grammar-token-subscription

<<<
6.3.2. Subscriptions

Subscription of a sequence (string, tuple or list) or mapping
(dictionary) object usually selects an item from the collection:

subscription ::=  primary "[" expression_list "]"

The primary must evaluate to an object that supports subscription (lists
or dictionaries for example). User-defined objects can support
subscription by defining a __getitem__() method.

For built-in objects, there are two types of objects that support
subscription:

If the primary is a mapping, the expression list must evaluate to an
object whose value is one of the keys of the mapping, and the
subscription selects the value in the mapping that corresponds to that
key. (The expression list is a tuple except if it has exactly one item.)

If the primary is a sequence, the expression list must evaluate to an
integer or a slice (as discussed in the following section).
>>>

continued and confirmed by:

https://docs.python.org/3/reference/datamodel.html#object.__getitem__

<<<
 object.__getitem__(self, key)

    Called to implement evaluation of self[key]. For sequence types, the
accepted keys should be integers and slice objects. Note that the
special interpretation of negative indexes (if the class wishes to
emulate a sequence type) is up to the __getitem__() method. If key is of
an inappropriate type, TypeError may be raised;
>>>


The "bi" part of "bisect" refers to "two" (as I'm sure you understand,
but just sayin'). There is also a concept of "equal" (cf one cake for
you and all the rest for me!).

Consider though, if the list is an even number of elements long
it can be halved, ie use the 'half' index to (after search
considerations) divide the whole list (conceptually) into two segments
of equal length.

If however, the list is an odd number of elements in length, halving the
length yields a float value and rounding/flooring that will yield two
segments of slightly-uneven, not-quite-half-length, segments!

The same applies when one bisects a segment.


NB I have to draw myself little block-diagrams in order to learn/to keep
track of ideas, such as the following (again, just sayin'!):-

[although this description follows the usual approach found in
text-books, the Python idiom may involve direct manipulation/trimming to
consider only the relevant segment of the original list, cf using
'pointers' to do the same, conceptually]


A KPI when implementing this algorithm is to keep track of the
indices/indexes representing the entire list, *and* those delimiting the
current segment under-search - most importantly: *not* losing an index
during some rounding-process!

The former is done for you by Python, ie a list's range is 0:len().

The code has to manage the latter - most illustrations use names such as
"top" and "bottom" (if you think/'see' of the arrangement vertically),
or "left" and "right", "begin" and "end", or similar. These refer to,
and define, the segment currently being searched.


Thus, to discuss <<<The "/" division works just fine but the "//"
doesn't work with the bisection search code.>>>. What may actually
happen is that Python auto-magically converts a calculated-to-be-float
index into an integer, and subsequently/consequently *that* test
'works'. Great stuff!


However!!!

If that is the case, then some list-element at a segment-boundary may
not be being included within the subsequent sub-segment, when it should.
Accordingly, a search where a 'missing index' also holds the answer,
will fail - or worse: conclude erroneously!


To (dis)prove this, may I suggest that you take (a copy of) the existing
code (could remove anything not related to the indices/indexes). Then
add debug-prints to show what is/not being included at each bisection
step. Try this with different lengths of list, and if you like, with
'the answer' located in different positions within the list. Ensure that
each element is considered, and/or none is ("silently") ignored!


Concluding with the problem of significant-digits and floats. It is
unlikely that any particular interest-rate will generate an exact
target-amount at the (exact) end of some time-period. Accordingly, if
interest is paid monthly, one waits until the end of the month, but then
the withdrawal will exceed 'the target' by some small amount. Thus,
being mathematically-precise, the required sum will be generated after
some number of months, plus a portion of the 'last' month.

Alternately, to round-out to an integral number of months, the
interest-rate can be 'tweaked' to give an exact answer as an integral
number of months - but should be limited in precision, per advice given.


Reinforcing @Wlfraed's advice, and something which has served me well
(and continues to do so!): when coding asymptotic solutions (and any
recursive routine) the first priority is to code 'how do I make it stop?'.

- or in my parlance: "where's the exit?", "the nearest exit may be
behind you", or "stop the world - I want to get off"!


Has this helped?
-- 
Regards,
=dn