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.

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

Uniform Generator hangs for certain limits. #1299

Closed
GUIpsp opened this issue Mar 8, 2023 · 7 comments · Fixed by #1462
Closed

Uniform Generator hangs for certain limits. #1299

GUIpsp opened this issue Mar 8, 2023 · 7 comments · Fixed by #1462

Comments

@GUIpsp
Copy link

GUIpsp commented Mar 8, 2023

See here for a MWE:

https://github.com/GUIpsp/rand_uniform_hang/blob/main/src/main.rs

I also tested that #1287 does not fix this issue.

@WarrenWeckesser
Copy link
Collaborator

WarrenWeckesser commented Mar 9, 2023

The "hang" is actually this loop

loop {
let mask = (scale * max_rand + low).ge_mask(high);
if !mask.any() {
break;
}
scale = scale.decrease_masked(mask);
}

taking a very long time to complete. That loop will require roughly spacing(low)/(2*spacing(scale)) iterations to complete, where spacing(x) is the unit of least precision of x. For the values in the MWE, this is 17179869184 iterations! Here's the calculation in a Python session:

In [52]: import numpy as np

In [53]: low = 0.99999999997819644

In [54]: high = 1.0

In [55]: scale = high - low

In [56]: np.spacing(low)/(2*np.spacing(scale))
Out[56]: 17179869184.0

The problem is that in the loop, scale is repeatedly decreased by the smallest possible amount until scale*max_rand + low is less than high. For inputs where high - low is much smaller than low, this will require a large number of iterations.

@dhardy
Copy link
Member

dhardy commented Mar 9, 2023

This is about float sampling so #1287 is unrelated; #1289 is more relevant (but I don't think it will solve this particular issue).

Decreasing the scale was added in #477 (@sicking).

@WarrenWeckesser
Copy link
Collaborator

FYI: NumPy has an issue about their uniform generator claiming to generate variates in [low, high) even though it can, in fact, generate high. The result of that discussion was to simply document that, because of floating point rounding, high might be generated in the output even though the underlying standard generator for [0, 1) guarantees that 1 is not generated.

@vks
Copy link
Collaborator

vks commented Mar 12, 2023

Floating point rounding is not a great excuse, it's easy to fix returning high by rejection sampling. You might still decide not to do that, i.e. for performance reasons, and users who cannot accept high being returned can do the rejection sampling themselves.

(FWIW, I ran into similar issues with the C++ standard libraries.)

@GUIpsp
Copy link
Author

GUIpsp commented Mar 13, 2023

I agree with whatr @vks, but in addition, I'd rather it return high than hit this degenerate case, having to wait for two hours.

@dhardy
Copy link
Member

dhardy commented Mar 13, 2023

but in addition, I'd rather it return high than hit this degenerate case, having to wait for two hours.

To be clear, this reported bug is not something we should just document and ignore.

The least intrusive fix would probably be to calculate a more precise decrement.


Uniform implements sampling for both [a, b) and [a, b], each for single-sample and distribution sampling. Perhaps we should simply by only supporting [a, b] (i.e. inclusive ranges)?

Complication: impl<X: SampleUniform> TryFrom<Range<X>> for Uniform<X> uses the half-open variant. We can simply subtract 1 for integer types — but there are no numeric traits in std and only rand_distr depends on num-traits.

@WarrenWeckesser
Copy link
Collaborator

The least intrusive fix would probably be to calculate a more precise decrement.

I think I have a fix. Once I work out one particular edge case, I'll submit a pull request.

WarrenWeckesser added a commit to WarrenWeckesser/rand that referenced this issue Mar 18, 2023
WarrenWeckesser added a commit to WarrenWeckesser/rand that referenced this issue Mar 18, 2023
WarrenWeckesser added a commit to WarrenWeckesser/rand that referenced this issue Mar 18, 2023
WarrenWeckesser added a commit to WarrenWeckesser/rand that referenced this issue Mar 18, 2023
@dhardy dhardy mentioned this issue Oct 31, 2023
23 tasks
dhardy added a commit that referenced this issue Jul 16, 2024
Fix #1299 by removing logic specific to ensuring that we emulate a
closed range by excluding `high` from the result.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

4 participants