Partially-sampled random numbers

[peteroupc]

I want to inform you of a concept called partially-sampled random numbers (PSRNs), which represent incomplete random numbers whose contents are sampled only as necessary. PSRNs are useful for implementing algorithms to sample from continuous distributions with arbitrary precision and without relying on floating-point arithmetic. I believe PSRNs may be useful to have in this library.

A partially-sampled random number stores a sign, an integer part, and a fractional part with an arbitrary number of digits.

I have written an article describing PSRNs in detail, as well as algorithms to sample PSRNs and certain continuous distributions, such as the beta distribution.

As you can see, supporting arithmetic and comparisons with PSRNs is anything but trivial. Neither is it trivial to describe an arbitrary-precision sampler for popular distributions, but I have done so for the beta, Rayleigh, and logistic distributions, and I have also added algorithms for adding, multiplying, and dividing PSRNs -- which was far from easy to do. Moreover, I am not a Rust programmer (so I can't provide a Rust implementation of these algorithms for now), but I want to make the PSRN concept better known, including here where the focus is on random number generation. This is one of the reasons I have written the PSRN article (as well as other articles on random sampling, including Bernoulli factory algorithms and the uniform sum/ratio distribution); another is to encourage others to develop new algorithms and new implementations for arbitrary-precision "exact" sampling (as Karney, for example, has done with the normal distribution in 2014-2016).

[dhardy]

My apology at making such a crude summary, but a PSRN is thus a structure containing:

• a partial value
• a reference to a generator able to sample additional bits/digits

?

In Rust, this is possible with a type something like the following:

struct PSRN<'a, R: Rng> {
    int_part: i32,
    frac_part: Vec<u32>,
    rng: &'a mut Rng,
}

The problem is, this requires one of:

1. a mutable borrow on the RNG (used above), preventing the RNG from being used for any other tasks until finished
2. locking logic (thread-safe or not) allowing the RNG to be used by multiple owners; this adds significant overhead
3. a child RNG, seeded from the parent, with the limitations of having to pick an algorithm and overhead of seeding it on-the-fly

Our distribution samplers (Beta, Uniform, etc.) already have a reference to the RNG which they can use to generate extra random bits, as required. Off the top of my head, I don't think we use this for arbitrary precision anywhere, but we already have implementations for high precision — the problem is, not everyone needs this much precision or wants the cost, and we didn't decide how to present users of the library with both options yet.

[peteroupc]

A PSRN is a pure data structure: it contains only an integer part, a fractional part, and a sign. Algorithms that operate on PSRNs are expected to provide (or access) an RNG separately from the PSRN data structure.

For example, say the PSRN stores base-10 digits. It could thus be expressed as follows:

1. A 32-bit integer part (i32 in Rust).
2. A vector of digits making up the fractional part. For instance, the vector could store {1, 5, 7} and thus represent a random number in the interval [0.157, 0.158].
3. A sign (a single bit that means either negative or non-negative). It may or may not be stored separately from the integer part.

Note the absence of an RNG here. As an example, say the PSRN stores a non-negative sign, an integer part of 98, and a fractional part {1, 5, 7}. It thus represents a random number in the interval [98.157, 98.158].

[vks]

This seems to be related to #1014, which discusses algorithms that sample bits only as needed.

[peteroupc]

In the meantime I have updated the partially-sampled random number (PSRN) article and numerous other open-source articles on random variate generation, including a page with more algorithms that operate on PSRNs. In these articles I put an emphasis on random variate generation:

• That exactly samples from a discrete distribution (such as Bernoulli factory algorithms).
• That samples from a continuous distribution with arbitrary precision and a user-specified accuracy.
• That avoids floating-point arithmetic.
• That avoids calculating transcendental functions when possible.

As a reminder, a PSRN consists of an integer part, a sign, and a fractional part containing an arbitrary number of digits.

[dhardy]

Sorry for the lack of interest here — I'm guessing PSRNs have applications in high-precision and arbitrary-precision arithmetic. But it sounds like a topic for a whole new library rather than something to be tacked on to the rand library.

I guess we'll just leave this issue here as a pointer to any one interested in pursuing it further.