C++11 subtract with carry engine random number generator

The C++11 subtract with carry engine(or subtract_with_carry_engine) produces unsigned random numbers.This engine also produces pseudorandom numbers like the linear_congruential_engine.

Link :C++11 random number generator

The declaration of the class is shown below.

template<class UIntType, size_t w, size_t s, size_t r>
class subtract_with_carry_engine;

The following relations shall hold:
0u < s ,
s < r ,
0 < w , and
w <= numeric_limits<UIntType>::digits
 
If any of the values passed as the template arguments during the object’s declaration does not agree with the above relation you will get an error.

**An algorithm of the engine is shown below,if you are only interested in the usage of the engine and not interested in how the algorithm works you can skip the next section.

Algorithm

To grasp the concept of the algorithm used by this engine,first of all consider a state of the engine as e_i.This state will consist of a sequence X_i of ‘r’ integer values such that 0 < X_i < 2^w,but note the subscript applied to X are to be taken modulo ‘r’.An instance of such sequence of x_i state is shown below,

x_i=X_i-r , … , X_i-s , … , X_i-1

i≥0 and it gives the state of the engine.

And the algorithm which produces the random number is shown below.

y= ( X_i-s – X_i-r – c ) mod 2^w.

c=1 if (X_i-s – X_i-r – c) > 1 else c is 0.

The ‘y’ value is the random number outputted by the engine.

The next section shown the types and member functions of the subtract_with_carry_engine class.

---

Types and characteristic

typedef UIntType result_type;

static constexpr size_t word_size = w;

static constexpr size_t short_lag = s;

static constexpr size_t long_lag = r;

static constexpr result_type min() { return 0; } 

static constexpr result_type max() { return m−1; }

static constexpr result_type default_seed = 19780503u; 

The min() and max() gives the smallest and largest number the engine can generate.

subtract_with_carry_engine< unsigned int , 4 , 100 , 300> swce ;

cout<< swce.min() << endl
<< swce.max();

Output,

Since the smallest number of unsigned type is 0, min() returns 0 and since the maximum value is always less than 2⁴,the next maximum value is 15 so max() returns 15.

---

---

Constructors

The C++11 subtract_with_carry_engine has two constructors.

explicit subtract_with_carry_engine(result_type value = default_seed);

template<class Sseq> explicit subtract_with_carry_engine(Sseq& q);

The first constructor will set the value to the default_seed value if no argument is passed to the constructor.It also act as the default constructor.

The second constructor is liable to be called only if the seed value passed is other than result_type,for instance if result_type is int type but if floating point value is passed as seed then the second constructor is called.

subtract_with_carry_engine<unsigned int , 4 , 100 , 300 > swce ; //calls the first constructor

subtract_with_carry_engine<unsigned int , 4 , 100 , 300> swce1(4.56) ; //calls the second constructor

---

Generating function

The generating function generates the random sequence.

result_type operator()( ); //Generate random sequence

void discard(unsigned long long z); //Jump to the 'z' state of the engine

operator()

To get the random sequence using the engine we will use the ‘operator()‘ function.

subtract_with_carry_engine<unsigned int , 4 , 100 , 300 > swce ;

cout<< swce() << ” ” << swce() ;

Output in Code::blocks,

discard(unsigned long long z)

The discard() function helps to skip some state of the engine thereby avoiding the random numbers generated by the engine in those state.The parameter ‘z’ determine how many state is skip by the engine ,if ‘z’ is 3 then the three states of engine is skip from the current state.And the following state of the engine is taken.Consider the code example below.

Note every engine object will produce the same random numbers as long as they are in the same state and the initial state of the engine is always same.

subtract_with_carry_engine<unsigned int , 4 , 100 , 300 > swce ,
  swce1 ; //swce and swce1 have the same state so they will generate same random sequence

for(auto i=0 ; i<6 ; i++)
{
cout<< swce() << ” “;
}

cout<< swce1() << ” ” ; //1st state output same as the first state output of swce 
cout<< swce() << endl ; //2nd state output same as the 2nd state output of swce

swce1.discard(3) ; //skip 3rd ,4th and 5th state

cout<< swce1() ; //6th state output same as the 6th state output of swce

Output

---

---

Seed generating functions

void seed(result_type s = default_seed);

template<class Sseq> void seed(Sseq& q); //a templatized version of the above function

The seed() functions allows you to divert the state of the engine from the normal consecutive state to some other sate and thus resulting in the generation of some random numbers different from the normal state.You can also use this function to set the state to the initial state of the engine.

subtract_with_carry_engine<unsigned int , 20 , 300 , 500 > swce ;

cout<< swce4( ) << ” ” << swce4( ) << ” ” << swce4( ) << endl ;

swce4.seed() ; //set the state to it’s initial state

cout<< swce4( ) << ” ” << swce4( ) << ” ” << swce4( ) << endl ;

Output in code::blocks,

You can also call the first seed() function if you want to avoid the generation of the same random sequence by passing the different argument every time you run the program.

---

operator== and operator!= functions

These two functions will test the state of the engine.The function operator== returns true if the engine will generate the same sequence in the future,in other word it returns true if the current state of the engines are same.The operator!= compares if the two engines have different state.

subtract_with_carry_engine<unsigned int , 20 , 300 , 500 > swce , swce1 ;

cout<< (swce==swce1) << endl ;

cout< swce() << ” ” << swce() << endl ;
cout< swc1() << ” ” << swce1() << endl ;

swce.seed(23) ; //change the state of the engine
swce1.seed(78) ; //change the state of the engine

cout<< (swce==swce1) << endl ;

cout< swce() << ” ” << swce() << endl ;
cout< swc1() << ” ” << swce1() << endl ;

Output in Code::blocks,

The initial state of swce and swce1 are the same so swce==swce1 gives 1(true) and the sequence generated is also the same.But,after calling seed() on swce and swce1 their states are changed,so ‘swce==swce1’ give 0(false) and also the generated sequence is different.

---

operator<< and operator>> functions

Using the operator<< we can significantly save the sate of the engine.The state saved can be reused later to produce exactly the same random sequence.

The engine’s state saved is obtained using the operator>> function.If bad input is encountered while acquiring the state,the state of the engine remains unchanged but the call to setstate(ios::failbit) is triggered which may throw ios::failure exception.

---