Random123
Loading...
Searching...
No Matches
Counter Based RNGs (CBRNGs).

The counter-based random number generators (CBRNGs) in the Random123 library are described in more detail in Parallel Random Numbers: As Easy as 1, 2, 3 , which was named the Best Paper at the ACM SC'11 International Conference on High Performance Computing, Networking, Storage, and Analysis. All the CBRNGs in the library conform to a consistent interface. Basically: 

    value = CBRNGname(counter, key)

Thus, with some care, they can be used interchangeably in applications. (Since code compiled with AES-NI instructions will result in an illegal instruction exception on processors without those instructions, Random123 provides a haveAESNI function that can be used to detect the existence of AES at run-time; user code could use it to either report an error or substitute an alternative compatible CBRNG.)

The API descriptions below are generic, but apply to all the different families of Random123 CBRNGs.

Fixed-size Array Types

Data is passed into and back from the Random123 functions as r123arrayNxW types; these types contain fixed-size arrays of W-bit types (uintW_t for the most part, but also a special r123m128i wrapper for the ARS and AESNI CBRNGs). The counter argument and the return value have the same type, referred to as ctr_type in C++, and ctr_t in C. The type of the key argument is referred to as key_type in C++, and key_t in C. For an r123arrayNxW, r, the data member r.v is an array of N elements, each of width W (each element is type uintW_t or an r123m128i wrapper object). C programs can access these elements as r.v[0], ... r.v[N-1] for the uintW_t types.

In C++, these array types closely resemble the C++0x std::array<N, uintW_t> template, but do not require C++11 libraries or compiler features. C++ programs can access array elements via operator[] r[0], ... r[N-1], or via most of the capabilities of a C++ "Container" e.g. at(), begin(), end(), size() and others. In addition, containers have incr() and incr(unsigned long long) member function that do increment-with-carry, which facilitate using r123arrays as very-long-period counters.

If the compiler environment supports it, Random123/array.h also declares r123array1xm128i, which contains an array of one r123m128i, which in turn is a class wrapping a single element of __m128i SSE type, which can be accessed as r.v[0].m. The r123::ARS1xm128i_R RNGs use r123array1xm128i for both ctr_type and key_type. For the AESNI RNG, ctr_type is an r123array1xm128i, but key_type is an opaque type, which must be initialized by assignment from a userkey_type (an r123array1xm128i).

A note on aliasing and type-punning

It is easiest (though not necessarily fastest) to choose a CBRNG whose ctr_type matches the width of the random data needed by the application, e.g., Philox4x32 for applications that need random data in 32-bit words. If the application's needs don't match the counter's value_type, it is tempting to use "type punning" and pointer casts to interconvert between types. Such conversions require great care and are very difficult to do safely without use of unions or memcpy. See here and here for discussions of the pitfalls related to aliasing. The C++ r123::ReinterpretCtr template is a safe way to reinterpret CBRNG counter types. Gcc's -Wstrict-aliasing=2 warning level will warn if strict aliasing violations are detected. If you find yourself ignoring or disabling warnings about strict aliasing, you should strongly consider adding something like gcc's -fnostrict-aliasing option to your compiler flags.

C++ API

There are four families of CBRNGs in the library:

A counter based RNG (CBRNG) with a name of the form FamilynameNxW is a type G with the three member typedefs:

  • G::ctr_type, which is an r123arrayNxW container class.
  • G::ukey_type, which is an r123arrayMxV container class. Note that the width, MxV of the key may not be the same as the width NxW of the ctr_type (Philox keys are half as wide as the counter, and future CBRNGs may well have different widths).
  • G::key_type, which in most cases is identical to G::ukey_type, but is different for the AESNI types. In all cases, there is a G::key_type(G::ukey_type) constructor and a G::key_type assignment operator for a G::ukey_type right-hand-side. In general, one can always write:
    G::ukey_type uk1, uk2;
    // user code initializes uk1 and uk2
    G::key_type k1(uk1), k2;
    k2 = uk2;

For most CBRNG's, i.e., any one not in the AESNI family, it is also perfectly acceptable to set the elements of a G::key_type directly from application variables. The quality of the results will not be compromised by using highly correlated or "non-random" keys.

A value g of type G can be invoked as g(c,k), where c is a value of type G::ctr_type and k is a value of type G::key_type, and g(c,k) returns a value of type G::ctr_type.

  • g() is a stateless, pure function. That is, g(c,k) may be called any number of times in any context and always returns the same result for the same inputs. In particular, c1==c2 and k1==k2 implies that g(c1,k1) == g(c2,k2).
  • For constant k, g(*,k) is a bijection. That is, g(c1,k) == g(c2,k) if and only if c1 == c2.
  • g "randomizes" its inputs. That is, for most sequences of inputs (c1,k1), (c2, k2), ... (including those obtained by following highly regular patterns of incrementing and striding through the counter and user key spaces) the output sequence, g(c1, k1), g(c2, k2), ... looks like a a sequence of uniformly distributed random variables drawn from the set of all ctr_types.

All the CBRNGs in the library work by iterating a randomization function for a specific number of rounds. Too few rounds and the CBRNG is a poor (perhaps catastrophically poor) random number generator. Too many rounds and time is wasted with little or no improvement in the randomness of the output. Each of the CBRNGs has a specific number of rounds which the authors believe is a reasonable compromise between speed and quality. In all cases, the default number of rounds includes a margin of safety above the minimum number of rounds that have passed all of the SmallCrush, Crush and BigCrush tests in the TestU01 suite.

Users may, however wish to employ a different numbers of rounds. Each of the above classes is actually a typedef of a more general class with a template parameter that specifies the number of rounds as name_rounds. The template classes all end in _R:

C API

A subset of the C++ interface is also directly usable by C programs. All header files may be safely included in C files. The C API to each of the supported RNGs consists of two typedefs, name_ctr_t, name_key_t, two functions name() and name_R(), and the enum name_rounds which specifies the recommended number of rounds.

  • name(c, k), performs the recommended number of rounds of the name CBRNG.
  • name_R(R,c,k), performs an R-round version of the name CBRNG. name(c,k) is equivalent to name_R(name_rounds, c, k).

The _R functions are designed and implemented so that an optimizing compiler can achieve good performance when the number of rounds is a compile-time constant. It is likely that philox4x32_R(10,c,k) will perform much better than philox4x32_R(r,c,k) if r cannot be evaluated at compile-time.

The supported names for the C API are

Generated on Mon Feb 24 2025 15:58:53 for Random123 by doxygen 1.12.0