Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

ranges with ambiguous lengths #20532

Closed
StefanKarpinski opened this issue Feb 8, 2017 · 7 comments
Closed

ranges with ambiguous lengths #20532

StefanKarpinski opened this issue Feb 8, 2017 · 7 comments
Assignees
@StefanKarpinski
Labels
collections Data structures holding multiple items, e.g. sets design Design of APIs or of the language itself ranges Everything AbstractRange

Comments

@StefanKarpinski
Copy link
Member

Uncommon failure case for range tests, observed by @JeffBezanson turns out to be somewhat philosophical: there are cases where n such that start + (n-1)*step == stop is not unique even when step != 0. Because floating-point. So the philosophical part is what should the length of a range be in such a case? The smallest viable choice of n? The largest viable choice of n?
@StefanKarpinski StefanKarpinski added the design Design of APIs or of the language itself label Feb 8, 2017
@StefanKarpinski StefanKarpinski self-assigned this Feb 8, 2017
StefanKarpinski added a commit that referenced this issue Feb 9, 2017
@StefanKarpinski
range tests: allow any range length that hits stop (#20532)
5102e6a 
This test was occasionally failing (~1 in 10 million times) since
there are cases where the length of such a range is ambiguous, i.e.
there is more than one `n` such that `start + (n-1)*step == stop`.
This adjusts the test to allow any such choice of range length.
@ararslan ararslan added the collections Data structures holding multiple items, e.g. sets label Feb 9, 2017
StefanKarpinski added a commit that referenced this issue Feb 9, 2017
@StefanKarpinski
range tests: allow any range length that hits stop (#20532)
9b7f840 
This test was occasionally failing (~1 in 10 million times) since
there are cases where the length of such a range is ambiguous, i.e.
there is more than one `n` such that `start + (n-1)*step == stop`.
This adjusts the test to allow any such choice of range length.
StefanKarpinski added a commit that referenced this issue Feb 9, 2017
@StefanKarpinski
range tests: allow any range length that hits stop (#20532)
b7ad743 
This test was occasionally failing (~1 in 10 million times) since
there are cases where the length of such a range is ambiguous, i.e.
there is more than one `n` such that `start + (n-1)*step == stop`.
This adjusts the test to allow any such choice of range length.
@StefanKarpinski
Copy link
Member Author

StefanKarpinski commented Feb 9, 2017 •
edited
Loading

I think that the closest viable value of n to (stop-start)/step would be a sane choice, and if both floor(Int, (stop-start)/step) and ceil(Int, (stop-start)/step) are viable, choose round(Int, (stop-start)/step).

StefanKarpinski added a commit that referenced this issue Feb 9, 2017
@StefanKarpinski
float ranges: for ambiguous length, use round((stop-start)/step)+1
ca6eb67 
Fixes #20532 by defining which length to use when there's more than
one length that is compatible with a given start:step:stop combo.
This also tightens the tests to check for that specific result.
@oscardssmith
Copy link
Member

Alternative suggestion, should an InexactError be thrown when eps(max(start,stop))>step? Ranges with floats are weird enough, but I think we should force users to pay attention to code that is almost certainly not behaving properly.

@lobingera
Copy link

just by curiosity: Does anyone know how matlab adresses this? I run the same code over a wide range of systems and OSs and the only thing i (afair) never had to revisit was linspace or ranges.

@timholy
Copy link
Member

timholy commented Feb 9, 2017

Always returns a length-1 range:

>> a = single(1.3173739)                         

a =

    1.3174

>> st = single(-2.3759904e-8)                

st =

   -2.3760e-8

>> a:st:a

ans =

    1.3174
>> linspace(a, a, 5)

ans =

    1.3174    1.3174    1.3174    1.3174    1.3174

@StefanKarpinski
Copy link
Member Author

StefanKarpinski commented Feb 9, 2017 •
edited
Loading

@lobingera: they do a hacky thing where if they hit the stop within a few arbitrary number of ulps, they consider it exact. Note that our implementation already works well enough that we essentially never get bug reports about it. This came up because I added more thorough tests that are wildly pathological some very rare fraction of the time. I have to run these tests tens of millions of times before I encounter these cases, so I'm not surprised you haven't encountered them in practice.

@StefanKarpinski
Copy link
Member Author

StefanKarpinski commented Feb 9, 2017 •
edited
Loading

@oscardssmith – it's a reasonable suggestion, but I think there are two cases here:

  1. You depend on/expect the range to have a specific length. This was the case in the tests I added. In this case, you'll quickly get your error since the length will not be what you expect.

  2. You don't. In that case, it seems better to give a range that has the right start, stop and step.

So picking a sensible choice like the length closest to (stop-start)/step + 1 seems to dominate raising an error in terms of usability.

@tkelman
Copy link
Contributor

tkelman commented Feb 9, 2017

moving the backport label to the PR #20533

StefanKarpinski added a commit that referenced this issue Feb 13, 2017
@StefanKarpinski
range tests: allow any range length that hits stop (#20532)
74bca9a 
(cherry picked from commit b7ad743)
StefanKarpinski added a commit that referenced this issue Feb 13, 2017
@StefanKarpinski
Fix computation of range length in certain cases (fix 0.5/#20373)
0cc3558 
This is the 0.5 edition: with this change a, b, n are always hit
exactly by a:s:a+n*s construction tests. There are two parts to
the fix: 1) check that the lifted rational endpoint is exact even
*after* we've reduced terms of the fractions; 2) apply the same
fix that I've proposed for the length in the non-lifted case.

Combined backport of these commits:

    - e849169
    - b7ad743

range tests: allow any range length that hits stop (#20532)

(cherry picked from commit b7ad743)
@simonbyrne simonbyrne added the ranges Everything AbstractRange label Jan 31, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@StefanKarpinski StefanKarpinski

Labels
collections Data structures holding multiple items, e.g. sets design Design of APIs or of the language itself ranges Everything AbstractRange
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
7 participants
@StefanKarpinski @timholy @simonbyrne @lobingera @tkelman @ararslan @oscardssmith