xso::generator — Jump Coefficients

We have a non-member function that returns the coefficients for the jump polynomial that can be used to efficiently move a generator or State ahead in its random number stream:

template<typename State>
std::array<typename State::word_type, State::word_count()>
xso::jump_coefficients(std::size_t N, bool N_is_pow2 = false)

template<typename State>
std::array<typename State::word_type, State::word_count()>
1xso::jump_coefficients(const State&, std::size_t N, bool N_is_pow2 = false)
1
The second version is a convenience that allows for calls like xso::jump_coefficients(rng, N) as opposed to xso::jump_coefficients<RNG>(N).

The template parameter State type can be either a full xso::generator or State class, as both have the methods needed for the function to succeed.

These functions return the coefficients of a polynomial that will jump the generator or State ahead by either \(J = N\) or \(J = 2^N\) steps. By default \(J = N\) but if the final argument is true, then \(J = 2^N\) which allows for huge jumps like \(J = 2^{100}\) that would overflow normal integer arguments.

Calls to this method will fail if the State does not have its pre-computed* characteristic coefficients embedded in the xoshiro.h header file. Calls will succeed for all the type aliased recommended generators.

The jump polynomial is returned as a set of coefficients packed into a std::array of words. That array can be passed to the jump function to perform multiple jumps of size \(J\).

The Idea

Suppose there are \(n\) bits of state packed into \(n_w\) words.

The corresponding transition matrix over \(\mathbb{F}_2\) will be \(n \times n\) and will be of full rank with a monic characteristic polynomial \(c(x)\).

For a jump \(J\) the jump polynomial is the residual of \(x^J\) with respect to \(c(x)\): \[ j(x; J) \equiv \mod{x^J}{c(x)}. \] For a given jump size \(J\) our function first gets the precomputed coefficients for \(c(x)\) by calling characteristic_coefficients.

Assuming it succeeds, it then performs the needed polynomial reduction to compute the coefficients of \(j(x; J)\): \[ j(x; J) = j_0 + j_1 x + \cdots + j_{n-1} x^{n-1}. \] The computation packs the \(n\) coefficients \(j_0, j_1, \ldots, j_{n-1}\) into \(n_w\) words of an array and returns them to the user. The jump method uses that array of coefficients to perform jumps of size \(J\).

The Details

The technique is fully explained in the jump technique page.

Example

#include <xoshiro.h>
#include <utilities/utilities.h>
int main()
{
    using rng = xso::rng;

1    std::size_t N = 100;
    bool N_is_pow2 = true;
    auto j = xso::jump_coefficients<rng>(N, N_is_pow2);
    std::print("Jump polynomial coefficients for 2^{} steps:\n{::#x}\n\n", N, j);

2    rng  g0;
3    auto g1 = g0;   xso::jump(g0, j);
4    auto g2 = g1;   xso::jump(g1, j);

    std::print("Some outputs from the different stream locations ...\n");
    for (std::size_t i = 0; i < 5; ++i)
        std::print("g0() = {:#x}\tg1() = {:#x}\tg2() = {:#x}\n", g0(), g1(), g2());
}
1
j is an array that has the coefficients of the jump polynomial for jumps of size \(2^{100}\).
2
g0 is a randomly seeded generator with 256 bits of state.
3
g1 is a copy of g0 with its state jumped forward by by \(2^{100}\) steps.
4
g2 is a copy of g0 with its state jumped forward by by \(2 \times 2^{100}\) steps.

Output: The stream values vary across runs

Jump polynomial coefficients for 2^100 steps:
1[0x1fe7835e4087fe62, 0xa797dd2a234c782b, 0x6bef1c2cbcff5536, 0xbf7e526feafe9fab]

Some outputs from the different stream locations ...
g0() = 0xa1948c61b3586d87       g1() = 0x66c8ab7ef1b5854d       g2() = 0xaa58e75a0f994f96
g0() = 0x3889856d621eb38d       g1() = 0x3ca9784b4851783f       g2() = 0xee2bd0800a4a6915
g0() = 0x4bd670c20f991bd3       g1() = 0xb7ac16efe1798c7f       g2() = 0x345a95aaed28520c
g0() = 0x7f03a920c24e889c       g1() = 0xb385d3c7b74b20fc       g2() = 0xcdab76d410b1f409
g0() = 0xabff23904d24f67        g1() = 0xd15f94305285313d       g2() = 0x92071bcea847b5ee
1
The return value from jump_coefficients isn’t hugely useful but can be used to jump to multiple locations in the random number stream.

See Also

characteristic_coefficients
jump
discard

Back to top