[BUG][FIX] Interval method includes:
Boris Gaertner
Boris.Gaertner at gmx.net
Thu Jun 17 13:29:23 UTC 2004
<germanmorales at deltasys.com>
took the time to review a proposed fix and found
a new problem:
>
> the fix by Boris efectively removes the bug it describes.
>
> while doing the fix, an #asFloat is removed from the calculation; so
> far I see no side effects, but perhaps someone put it in there for some
> special case I can't imagine now, so this could be problematic
>
> reviewing the original implementation, I see that while it pretends to
> avoid going through the list of possible values, this leads to extrange
> answers like the following one:
>
> (1 to: 5 by: 1) includes: 2 > obvioulsy true
> (1 to: 5 by: 1) includes: 2.5 > obvioulsy false
> (100000000000000 to: 500000000000000 by: 100000000000000)
> includes: 200000000000000 > true as before, I just put some zeros
> behind, so what?
> (100000000000000 to: 500000000000000 by: 100000000000000)
> includes: 250000000000000 > true! what? yes, try it yourself!
>
> I'm attaching a version that fixes this problem and the previous one,
> but perhaps introduces new failing cases, please someone (less asleep
> than me) review it.
>
> German Morales
>
Thank you a lot for this review, German!
I will rewrite your example as a test case and post
it separately with the [TEST] prefix.
The bug that you reported is also present in my
proposed method #indexOf:startingAt:ifAbsent:
but more about that later.
It is very obvious that you found a bug, but this
morning I found it surprisingly difficult to explain
* what is wrong
* and why your fix is correct.
I even wonder whether I am less clever than the
average of Smalltalkers, but for the benefit of
those interested in the topic (and for my own
benefit, of course) I write down what I
think is an understandable reasoning:
Interval>>includes: does two checks:
1. First, the given number is checked against the
interval bounds.
2. If the number is within the interval bounds,
the method #valuesInclude: checks whether
aNumber is an element of the infinite set:
{ val*step + start  val isInteger }
So we have to aske whether there exists an
integer val that satisfies the equation:
aNumber = (val *step + start).
We can easily solve this equation for val
and obtain  now already written in Smalltalk:
 val 
val := (aNumber  self first) / self increment.
^val isInteger
This is the correct solution for as long as no floats
are involved. The test 'isInteger' is really simple
and in the absence of floats it is sufficient.
I had this in mind why I removed the #asFloat
from the original version, but I understand now
that I did not enough. I failed to elaborate a
correct algorithm that identifies floats
that are close to an integer value.
val fractionPart abs < 1.0e10
is such an algorithm and we can conclude
that your proposal is correct. The method
#fractionPart is also available for integers
and fractions and therefore your proposal
remains correct when we avoid early conversion
to floats.
Usually I try to avoid floats, but that is a matter
of personal preferences. However, when we prefer
to compute without floats for as long as possible,
we have to compute with fractions and the
computation of the fractional part of a fraction
of two large integers is perhaps a bit time consuming.
I think now that it is perhaps best to write:
valuesInclude: aNumber
 val 
val _ (aNumber  self first) / self increment.
^val isFloat
ifTrue: [val fractionPart abs < 1.0e10]
ifFalse: [val isInteger]
This version uses exact calculation without
floats whenever that is possible. It also
avois unnecessary computations with
fractions.
========================
As mentioned earlier, Germans fix is also
needed for the method
indexOf:startingAt:ifAbsent:
that I proposed yesterday.
Looking a bit closer into the collection
hierarchy, I found that SequenceableCollection,
the direct superclass of Interval, implements
#includes: in this way:
includes: anElement
^(self indexOf: anElement) ~= 0
That's it!
We do not really have to redefine #includes:
in Interval for speed, it is sufficient to have a fast
definition for computation of the element index.
This is easy to do, because we can
reuse parts of #valuesInclude:
which computes a zerobased index.
The attached change set is a proposal for the
use of the inherited #includes: It contains a
new version of
indexOf:startingAt:ifAbsent:
and it drops the methods
#includes: and #valuesInclude:
So we improved #valuesInclude: just to
drop it after using its essence in a different method!
Greetings, Boris
 next part 
A nontext attachment was scrubbed...
Name: IntervalIndexFixbg.1.cs
Type: application/octetstream
Size: 1511 bytes
Desc: not available
Url : http://lists.squeakfoundation.org/pipermail/squeakdev/attachments/20040617/767731e1/IntervalIndexFixbg.1.obj
More information about the Squeakdev
mailing list
