Function malachite_nz::natural::random::random_natural_inclusive_range

pub fn random_natural_inclusive_range(
    seed: Seed,
    a: Natural,
    b: Natural,
    mean_bits_numerator: u64,
    mean_bits_denominator: u64
) -> RandomNaturalRange 

Generates random Naturals in the closed interval $[a, b]$.

In general, the Naturals are not generated uniformly; for that, use uniform_random_natural_inclusive_range. Instead, Naturals 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 Naturals 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, ...]"
)