377 lines
13 KiB
Plaintext
377 lines
13 KiB
Plaintext
///////////////////////////////////////////////////////////////////////////
|
|
// FILE: type_traits
|
|
//
|
|
// =========================================================================
|
|
//
|
|
// Open Watcom Project
|
|
//
|
|
// Copyright (c) 2004-2010 The Open Watcom Contributors. All Rights Reserved.
|
|
//
|
|
// This file is automatically generated. Do not edit directly.
|
|
//
|
|
// =========================================================================
|
|
//
|
|
// Description: This header is part of the C++ standard library extentions
|
|
// TR1 as currently defined in n1836
|
|
///////////////////////////////////////////////////////////////////////////
|
|
#ifndef _RANDOM_INCLUDED
|
|
#define _RANDOM_INCLUDED
|
|
|
|
#ifndef _ENABLE_AUTODEPEND
|
|
#pragma read_only_file;
|
|
#endif
|
|
|
|
#ifndef __cplusplus
|
|
#error This header file requires C++
|
|
#endif
|
|
|
|
#include <cstdint>
|
|
|
|
namespace _ow {
|
|
/*---------------------------------------------------------------
|
|
* helpers
|
|
*/
|
|
template< class T, T x >
|
|
struct bit_count{
|
|
enum{ value = bit_count< T, (x>>1) >::value + (x & 1) };
|
|
};
|
|
template< class T >
|
|
struct bit_count< T, 0 >{
|
|
enum{ value = 0 };
|
|
};
|
|
|
|
// returns integer part of log base 2 of x
|
|
template< class UIntType, UIntType x >
|
|
struct log_base2{
|
|
enum{ value = log_base2< UIntType, (x>>1) >::value + 1 };
|
|
};
|
|
template< class UIntType >
|
|
struct log_base2< UIntType, 1 >{
|
|
enum{ value = 0 };
|
|
};
|
|
template< class UIntType >
|
|
struct log_base2< UIntType, 0 >{
|
|
//define zero as log(max UIntType + 1)
|
|
enum{ value = sizeof(UIntType)*8 };
|
|
};
|
|
|
|
|
|
/*---------------------------------------------------------------
|
|
* modulo multiplication constant by variable
|
|
* main wrapper
|
|
* x and c must be modulo m
|
|
*/
|
|
template< class UIntType, UIntType c, UIntType m >
|
|
struct modulo_mult{
|
|
UIntType operator()( UIntType x ){
|
|
//static_assert( (m == 0) || (c < m), "multiplier must be modulo m" );
|
|
//assert x < m
|
|
modulo_mult_detail< UIntType, m,// c, m
|
|
// spec 1 if m = 2^n, 0 is special case meaning use mod type max + 1
|
|
bit_count< UIntType, m >::value == 1 || ( m == 0 ),
|
|
// spec 2 if c < root m
|
|
c <= m/c, // c*c < m
|
|
// spec 3 if m = 2^n-1
|
|
(m != 0) && (bit_count< UIntType, m+1 >::value == 1) || (bit_count< UIntType, m+1 >::value == 0)
|
|
> mult;
|
|
return( mult(c,x) );
|
|
}
|
|
};
|
|
|
|
/*---------------------------------------------------------------
|
|
* modulo multiplication
|
|
* general case - hmm, complicated need to think about this one
|
|
*/
|
|
template< class UIntType, UIntType m, bool p2, bool schrage, bool p2_1 >
|
|
struct modulo_mult_detail{
|
|
UIntType operator()( UIntType c , UIntType x ){
|
|
//static_assert(0,"not yet implemented");
|
|
//std::cout<<"not yet implemented "<<m<<" "<<c<<" "<<x<<"\n";
|
|
return 0;
|
|
}
|
|
};
|
|
/*---------------------------------------------------------------
|
|
* modulo multiplication
|
|
* specialised for Schrage's method
|
|
*/
|
|
template< class UIntType, UIntType m >
|
|
struct modulo_mult_detail< UIntType, m, false, true, false >{
|
|
UIntType operator()( UIntType c, UIntType x ){
|
|
//std::cout<<"Schrage method c="<<c<<" x="<<x<<" m="<<m<<"\n";;
|
|
// Schrage's method
|
|
UIntType const q = m / c;
|
|
UIntType const r = m % c;
|
|
UIntType k = x / q;
|
|
UIntType j = x % q;
|
|
//x = c * ( x % q ) - r * ( x / q );
|
|
UIntType g = c * j;
|
|
UIntType h = r * k;
|
|
//if( g < h ) x = g - h + m;
|
|
//else x = g - h;
|
|
return( (g < h) ? (g - h + m ) : (g - h) );
|
|
}
|
|
};
|
|
/*---------------------------------------------------------------
|
|
* modulo multiplication
|
|
* specialised for m power of 2
|
|
*/
|
|
template< class UIntType, UIntType m,bool b >
|
|
struct modulo_mult_detail< UIntType, m, true, b, false >{
|
|
UIntType operator()( UIntType c, UIntType x ){
|
|
//std::cout<<"mult mod power of 2\n";
|
|
return( (c * x) & (m - 1) );
|
|
}
|
|
};
|
|
/*---------------------------------------------------------------
|
|
* modulo multiplication
|
|
* specialised for m = n^2-k, currently where k 1
|
|
* !!TODO!! : extend for k is 'small', get rid of long long,
|
|
* specialise with hand coded assembly
|
|
*/
|
|
template< class UIntType, UIntType m, bool b >
|
|
struct modulo_mult_detail< UIntType, m, false, b, true >{
|
|
UIntType operator()( UIntType c, UIntType x ){
|
|
//std::cout<<"mult mod power of 2 - 1\n";
|
|
//fix me
|
|
UIntType const n = _ow::log_base2<UIntType, m+1>::value;
|
|
unsigned long long t = (unsigned long long)c*x;
|
|
unsigned long long t2, t3;
|
|
t2 = t >> n;
|
|
t3 = ( t + t2 + 1 ) >> n;
|
|
t2 = t - t3 * m;
|
|
return( UIntType( t2 ) );
|
|
}
|
|
};
|
|
|
|
|
|
/*---------------------------------------------------------------
|
|
* modulo addition constant by variable
|
|
* main wrapper
|
|
* c and x should be mod m to start with
|
|
*/
|
|
template< class UIntType, UIntType c, UIntType m >
|
|
struct modulo_add{
|
|
UIntType operator()( UIntType x ){
|
|
modulo_add_detail< UIntType,
|
|
// true if m is power of 2
|
|
bit_count< UIntType, m >::value == 1,
|
|
c == 0
|
|
> add;
|
|
return( add(c,x,m) );
|
|
}
|
|
};
|
|
|
|
/*---------------------------------------------------------------
|
|
* modulo addition
|
|
* general case
|
|
*/
|
|
template< class UIntType, bool b1, bool b2>
|
|
struct modulo_add_detail{
|
|
UIntType operator()( UIntType c , UIntType x , UIntType m ){
|
|
// if x + c > m : x = x +c - m, else : x = x + c
|
|
// transform to
|
|
// if x > m - c : x = x - (m-c), else : x = x + c
|
|
// because c < m, m-c > 0 and no overflows :o)
|
|
UIntType const d = m - c;
|
|
return( ( x > d ) ? ( x - d ) : ( x + c ) );
|
|
}
|
|
};
|
|
/*---------------------------------------------------------------
|
|
* modulo addition
|
|
* specialised for m = n^2
|
|
*/
|
|
template< class UIntType >
|
|
struct modulo_add_detail< UIntType, true, false >{
|
|
UIntType operator()( UIntType c, UIntType x, UIntType m ){
|
|
return( ( x + c ) & ( m - 1 ) );
|
|
}
|
|
};
|
|
/*---------------------------------------------------------------
|
|
* modulo addition
|
|
* specialised for c = 0
|
|
*/
|
|
template< class UIntType >
|
|
struct modulo_add_detail< UIntType, false, true>{
|
|
UIntType operator()( UIntType c, UIntType x, UIntType m ){
|
|
//std::cout<<"mod add 0\n";
|
|
c=c; m=m;
|
|
return( x );
|
|
}
|
|
};
|
|
} // namespace _ow
|
|
|
|
|
|
namespace std {
|
|
namespace tr1 {
|
|
|
|
template< class UIntType, UIntType a, UIntType c, UIntType m >
|
|
class linear_congruential{
|
|
public:
|
|
// types
|
|
typedef UIntType result_type;
|
|
|
|
// parameter values
|
|
static const UIntType multiplier = a;
|
|
static const UIntType increment = c;
|
|
static const UIntType modulus = m;
|
|
|
|
// constructors
|
|
explicit linear_congruential( unsigned long x0 = 1 ) : x(x0) {}
|
|
|
|
template< class Gen > linear_congruential( Gen& g ){};
|
|
|
|
// member functions
|
|
void seed( unsigned long x0 = 1 );
|
|
template< class Gen > void seed( Gen& g );
|
|
result_type min() const;
|
|
result_type max() const;
|
|
result_type operator()()
|
|
{// has to be inline, compiler doesn't like non type params at the moment
|
|
// x = ( a * x + c ) % m;
|
|
// x = ( ( a*x ) % m + c ) %m
|
|
_ow::modulo_mult< UIntType, a, m > mm;
|
|
x = mm( x );
|
|
// add the constant
|
|
_ow::modulo_add< UIntType, c, m > aa;
|
|
x = aa( x );
|
|
return( x );
|
|
}
|
|
private:
|
|
UIntType x; // state
|
|
};// end class linear_congruential
|
|
|
|
// to do - specialise for 2^n - x where x is small and x is 0
|
|
|
|
typedef std::tr1::linear_congruential< std::tr1::uint32_t, 16807, 0, (1<<31)-1 > minstd_rand0;
|
|
typedef std::tr1::linear_congruential< std::tr1::uint32_t, 48271, 0, (1<<31)-1 > minstd_rand;
|
|
|
|
|
|
// ===========================================================================
|
|
|
|
template< class UIntType, int w, int n, int m, int r, UIntType a,
|
|
int u, int s, UIntType b, int t, UIntType c, int l >
|
|
class mersenne_twister{
|
|
public:
|
|
// types
|
|
typedef UIntType result_type;
|
|
// parameter values
|
|
// ??? what is the point of these???
|
|
static const int word_size = w;
|
|
static const int state_size = n;
|
|
static const int shift_size = m;
|
|
static const int mask_bits = r;
|
|
static const UIntType parameter_a = a;
|
|
static const int output_u = u;
|
|
static const int output_s = s;
|
|
static const UIntType output_b = b;
|
|
static const int output_t = t;
|
|
static const UIntType output_c = c;
|
|
static const int output_l = l;
|
|
|
|
// constructors and member functions
|
|
mersenne_twister() : i(0),i_m(m-1) { seed();}
|
|
explicit mersenne_twister( unsigned long v ) : i(0),i_m(m-1) { seed(v); }
|
|
template<class Gen> mersenne_twister(Gen& g){};
|
|
void seed(){ seed( 5489 ); }
|
|
void seed( unsigned long v )
|
|
{
|
|
// Sets x(-n) to vmod2w. Then, iteratively, sets
|
|
// x(-n+i) = (i+1812433253(x(-n+i-1) xor (x(-n+i-1) rshift (w-2)))mod 2^w
|
|
x[0] = v;
|
|
for( int i = 1; i < n; i++ ){
|
|
UIntType const mask = (1 << (w-1)) + ((1 << (w-1)) - 1);
|
|
x[i] = ( i + 1812433253UL * ( x[i-1] ^ ( x[i-1] >> (w-2) ) ) )
|
|
& mask;
|
|
}
|
|
}
|
|
//template<class Gen> void seed(Gen& g);
|
|
result_type min() const;
|
|
result_type max() const;
|
|
result_type operator()()
|
|
{
|
|
// see also "Mersenne Twister: A 623-dimensionally equidistributed
|
|
// uniform pseudorandom number generator"
|
|
// Makoto Matsumoto and Takuji Nishimura 1998
|
|
|
|
// I wondered whether calculating blocks at a time is bad on
|
|
// modern processor because of unnecessary comparisons and jumps
|
|
// Little difference on p4 northwood and seems rather tetchy to
|
|
// differences in way coded/optimisation settings that change order
|
|
// of instruction/regs used
|
|
// Would be interested to see how it fairs on other processors (amd?)
|
|
// see bench/owstl
|
|
|
|
UIntType y;
|
|
int z, i_1;
|
|
UIntType const um = -1 << r; // top w-r bits set, low r clear
|
|
UIntType const lm = (1 << r)-1; // bottom r bits set
|
|
|
|
// inc i mod n
|
|
i_1 = i + 1;
|
|
z = (signed int)(i_1 - n) >> 31; // z = 0 if overflowed 111... otherwise
|
|
i_1 &= z;
|
|
|
|
// inc (i+m) mod n
|
|
i_m++;
|
|
z = (signed int)(i_m - n) >> 31; // z = 0 if overflowed 111... otherwise
|
|
i_m &= z;
|
|
|
|
// first part of recurence equation
|
|
y = (x[i] & um) | (x[i_1] & lm);
|
|
|
|
// multiply by 'matrix A'
|
|
// means xor shifted y with vector a if low bit of y set
|
|
y = (a & -(y&1)) ^ (y>>1);
|
|
|
|
// finish off equation
|
|
y = x[i_m] ^ y;
|
|
x[i] = y;
|
|
|
|
// increment state pointer
|
|
i = i_1;
|
|
|
|
// temper output
|
|
y = y ^ ( y >> u );
|
|
y = y ^ ( y << s ) & b;
|
|
y = y ^ ( y << t ) & c;
|
|
y = y ^ ( y >> l );
|
|
|
|
return( y );
|
|
}// end operator()
|
|
private:
|
|
UIntType x[n];
|
|
size_t i,i_m;
|
|
};// end mersenne_twister
|
|
|
|
typedef mersenne_twister< uint32_t,32,624,397,
|
|
31,0x9908b0df,11,7,0x9d2c5680,
|
|
15,0xefc60000,18> mt19937;
|
|
|
|
} // namespace tr1
|
|
} // namespace std
|
|
|
|
namespace _watcom {
|
|
|
|
// to do - would like to add WELL generator
|
|
|
|
/* also see "tables of lenear congruential generators of different sizes
|
|
and good lattice structure" Pierre L'Ecuyer.
|
|
I guess we could create some statistical tests, try out a few and
|
|
provide some potetially useful ones here ? */
|
|
|
|
typedef std::tr1::linear_congruential< std::tr1::uint32_t, 1588635695, 0, (1<<32)-5 > lcg325a;
|
|
typedef std::tr1::linear_congruential< std::tr1::uint64_t, 2862933555777941757, 0, (1<<64) > lcg64a;
|
|
typedef std::tr1::linear_congruential< std::tr1::uint32_t, 2891336453, 1, (1<<32) > lcg32;
|
|
typedef std::tr1::linear_congruential< std::tr1::uint32_t, 37769685, 1, (1<<31) > lcg31;
|
|
// to do
|
|
|
|
// useful MT typedefs see Matsumoto & Nishimura 1998
|
|
// w, n, m, r, a, u, s, b, t, c, l
|
|
typedef std::tr1::mersenne_twister< std::tr1::uint32_t, 32, 351, 175, 19,
|
|
0xE4BD75F5, 11, 7, 0x655E5280, 15, 0xFFD58000, 17 > mt11213a;
|
|
// to do
|
|
|
|
} // namespace _watcom
|
|
|
|
#endif
|