Function malachite_nz::natural::random::random_natural_range_to_infinity

pub fn random_natural_range_to_infinity(
    seed: Seed,
    a: Natural,
    mean_bits_numerator: u64,
    mean_bits_denominator: u64
) -> RandomNaturalRangeToInfinity 

Generates random Naturals greater than or equal to a lower bound $a$.

The mean bit length $m$ of the Naturals is specified; it must be greater than the bit length of $a$. $m$ is equal to mean_bits_numerator / mean_bits_denominator.

The actual bit length is chosen from a geometric distribution with lower bound $a$ and mean $m$. Then a Natural is chosen uniformly among all Naturals with that bit length that are greater than or equal to $a$. The resulting distribution has no mean or higher-order statistics (unless $a < m < a + 1$, which is not typical).

$$ P(n) = \begin{cases} 0 & \text{if} \quad n < a, \\ \frac{1}{m+1} & \text{if} \quad a = n = 0, \\ \frac{m}{(m+1)^2}\left ( \frac{m}{2(m+1)} \right )^\nu & \text{if} \quad 0 = a < n, \\ \frac{1}{(2^{\nu + 1}-a)(m-\alpha)} & \text{if} \quad 0 < a \ \text{and} \ \alpha = \nu, \\ \frac{\left ( 1 - \frac{1}{\alpha-m}\right )^{\nu-\alpha}}{2^\nu(m-\alpha)} & \text{if} \quad 0 < a \ \text{and} \ \alpha < \nu, \\ \end{cases} $$ where $\alpha = \lfloor \log_2 a \rfloor$ and $\nu = \lfloor \log_2 n \rfloor$.

The output length is infinite.

Expected complexity per iteration

$T(n, m) = O(n + m)$

$M(n, m) = O(n / m)$

where $T$ is time, $M$ is additional memory, $n$ is mean_precision_numerator, and $m$ is mean_precision_denominator.

Panics

Panics 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_range_to_infinity;
use malachite_nz::natural::Natural;

assert_eq!(
    prefix_to_string(
        random_natural_range_to_infinity(EXAMPLE_SEED, Natural::from(1000u32), 20, 1),
        10
    ),
    "[3254, 4248, 163506, 1189717027294, 5282, 12220, 60088, 1016911, 5772451, 5473099750562, \
    ...]"
)