Function malachite_nz::natural::random::random_natural_inclusive_range
source · pub fn random_natural_inclusive_range(
seed: Seed,
a: Natural,
b: Natural,
mean_bits_numerator: u64,
mean_bits_denominator: u64
) -> RandomNaturalRange ⓘ
Expand description
Generates random Natural
s in the closed interval $[a, b]$.
In general, the Natural
s are not generated uniformly; for that, use
uniform_random_natural_inclusive_range
. Instead, Natural
s with smaller bit lengths are
generated more frequently.
The distribution of generated values is parametrized by a number $m$, given by
mean_bits_numerator / mean_bits_denominator
. It is not actually the mean bit length, though it
approaches the mean bit length as $\log (b/a)$ approaches infinity. $m$ must be greater than
$a$, but it may be arbitrarily large. The smaller it is, the more quickly the probabilities
decrease as bit length increases. The larger it is, the more closely the distribution approaches
a uniform distribution over the bit lengths.
Once a bit length is selected, the Natural
is chosen uniformly from all Natural
s with
that bit length that are in $[a, b]$.
$$ P(n) = \begin{cases} 0 & \text{if} \quad n < a \ \text{or} \ n > b, \\ 1 & \text{if} \quad a = n = b = 0, \\ \frac{1}{b-a} & \text{if} \quad 0 < a \ \text{and} \ \alpha = \beta, \\ \left [ (m+1)\left ( 1-\left (\frac{m}{m+1}\right )^{\beta+2} \right ) \right ]^{-1} & \text{if} \quad 0 = a = n < b \\ (2^{\alpha+1}-n)\left [ (m-\alpha)\left ( 1+\frac{1}{\alpha-m}\right )^{\alpha-\nu}- (m-\alpha-1)\left ( 1+\frac{1}{\alpha-m}\right )^{\beta-\nu}\right ]^{-1} & \text{if} \quad 0 < a \ \text{and} \ \alpha = \nu < \beta, \\ \frac{m^{\nu+1}(m+1)^{\beta-\nu}}{((m+1)^{\beta+2}-m^{\beta+2})(2^\beta-n+1)} & \text{if} \quad 0 = a < n \ \text{and} \ \nu = \beta, \\ (n-2^\beta+1)\left [ (m-\alpha)\left ( 1+\frac{1}{\alpha-m}\right )^{\alpha-\nu}- (m-\alpha-1)\left ( 1+\frac{1}{\alpha-m}\right )^{\beta-\nu}\right ]^{-1} & \text{if} \quad 0 < a \ \text{and} \ \alpha < \nu = \beta, \\ \frac{m(m+1)^\beta \left ( \frac{m}{2(m+1)}\right )^\nu}{(m+1)^{\beta+2}-m^{\beta+2}} & \text{if} \quad 0 = a < n \ \text{and} \ \nu < \beta, \\ 2^{-\nu}\left [ (m-\alpha)\left ( 1+\frac{1}{\alpha-m}\right )^{\alpha-\nu}-(m-\alpha-1) \left ( 1+\frac{1}{\alpha-m}\right )^{\beta-\nu}\right ]^{-1} & \text{if} \quad 0 < a \ \text{and} \ \alpha < \nu < \beta, \end{cases} $$ where $\alpha = \lfloor \log_2 a \rfloor$, $\beta = \lfloor \log_2 b \rfloor$, and $\nu = \lfloor \log_2 n \rfloor$.
The output length is infinite.
§Expected complexity per iteration
$T(n) = O(n)$
$M(m) = O(m)$
where $T$ is time, $M$ is additional memory, $n$ is mean_bits_numerator + mean_bits_denominator
, and $m$ is b.significant_bits()
.
§Panics
Panics if $a > b$, if mean_bits_numerator
or mean_bits_denominator
are zero, if their ratio
is less than or equal to $a$, or if they are too large and manipulating them leads to arithmetic
overflow.
§Examples
use malachite_base::iterators::prefix_to_string;
use malachite_base::random::EXAMPLE_SEED;
use malachite_nz::natural::random::random_natural_inclusive_range;
use malachite_nz::natural::Natural;
assert_eq!(
prefix_to_string(
random_natural_inclusive_range(
EXAMPLE_SEED,
Natural::from(1000u32),
Natural::from(1000000000u32),
20,
1
),
10
),
"[3254, 4248, 163506, 600542, 5282, 12220, 60088, 1016911, 5772451, 2792610, ...]"
)