lemon-1.0: comparison lemon/random.h

equal deleted inserted replaced

-:0191b7b84be9
+:c96cd362b78b
-/* -*- C++ -*-
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
 *
-* This file is a part of LEMON, a generic C++ optimization library
+* This file is a part of LEMON, a generic C++ optimization library.
 *
 * Copyright (C) 2003-2008
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 /*
 * This file contains the reimplemented version of the Mersenne Twister
 * Generator of Matsumoto and Nishimura.
 *
 * See the appropriate copyright notice below.
 *
 * Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * 3. The names of its contributors may not be used to endorse or promote
 *    products derived from this software without specific prior written
 *    permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 ///\brief Mersenne Twister random number generator
 namespace lemon {
 namespace _random_bits {
 template <typename _Word, int _bits = std::numeric_limits<_Word>::digits>
 struct RandomTraits {};
 template <typename _Word>
 struct RandomTraits<_Word, 32> {
 typedef _Word Word;
 static const int bits = 32;
 static const int length = 624;
 static const int shift = 397;
 static const Word mul = 0x6c078965u;
 static const Word arrayInit = 0x012BD6AAu;
 static const Word arrayMul1 = 0x0019660Du;
 static const Word arrayMul2 = 0x5D588B65u;
 void initState() {
 static const Word seedArray[4] = {
 0x12345u, 0x23456u, 0x34567u, 0x45678u
 };
 initState(seedArray, seedArray + 4);
 }
 void initState(Word seed) {
 static const Word mul = RandomTraits<Word>::mul;
 current = state;
 Word *curr = state + length - 1;
 curr[0] = seed; --curr;
 for (int i = 1; i < length; ++i) {
 curr[0] = (mul * ( curr[1] ^ (curr[1] >> (bits - 2)) ) + i);
 initState(init);
 num = length > end - begin ? length : end - begin;
 while (num--) {
 curr[0] = (curr[0] ^ ((curr[1] ^ (curr[1] >> (bits - 2))) * mul1))
 + *it + cnt;
 ++it; ++cnt;
 if (it == end) {
 it = begin; cnt = 0;
 }
 if (curr == state) {
 curr = state + length - 1; curr[0] = state[0]; --curr;
 cnt = 1;
 }
 }
 state[length - 1] = Word(1) << (bits - 1);
 }
 void copyState(const RandomCore& other) {
 std::copy(other.state, other.state + length, state);
 current = state + (other.current - other.state);
 }
 return RandomTraits<Word>::tempering(rnd);
 }
 private:
 void fillState() {
 static const Word mask[2] = { 0x0ul, RandomTraits<Word>::mask };
 static const Word loMask = RandomTraits<Word>::loMask;
 static const Word hiMask = RandomTraits<Word>::hiMask;
 current = state + length;
 register Word *curr = state + length - 1;
 register long num;
 num = length - shift;
 while (num--) {
 curr[0] = (((curr[0] & hiMask) | (curr[-1] & loMask)) >> 1) ^
 curr[- shift] ^ mask[curr[-1] & 1ul];
 --curr;
 state[0] = (((state[0] & hiMask) | (curr[length - 1] & loMask)) >> 1) ^
 curr[length - shift] ^ mask[curr[length - 1] & 1ul];
 }
 Word *current;
 Word state[length];
 };
 template <typename Result,
 int shift = (std::numeric_limits<Result>::digits + 1) / 2>
 struct Masker {
 static Result mask(const Result& result) {
 return Masker<Result, (shift + 1) / 2>::
 mask(static_cast<Result>(result | (result >> shift)));
 }
 };
 template <typename Result>
 struct Masker<Result, 1> {
 static Result mask(const Result& result) {
 return static_cast<Result>(result | (result >> 1));
 }
 };
 template <typename Result, typename Word,
 int rest = std::numeric_limits<Result>::digits, int shift = 0,
 bool last = rest <= std::numeric_limits<Word>::digits>
 struct IntConversion {
 static const int bits = std::numeric_limits<Word>::digits;
 static Result convert(RandomCore<Word>& rnd) {
 return static_cast<Result>(rnd() >> (bits - rest)) << shift;
 }
 };
 template <typename Result, typename Word, int rest, int shift>
 struct IntConversion<Result, Word, rest, shift, false> {
 static const int bits = std::numeric_limits<Word>::digits;
 static Result convert(RandomCore<Word>& rnd) {
 return (static_cast<Result>(rnd()) << shift) |
 IntConversion<Result, Word, rest - bits, shift + bits>::convert(rnd);
 }
 };
 template <typename Result, typename Word,
 bool one_word = (std::numeric_limits<Word>::digits <
-			       std::numeric_limits<Result>::digits) >
+std::numeric_limits<Result>::digits) >
 struct Mapping {
 static Result map(RandomCore<Word>& rnd, const Result& bound) {
 Word max = Word(bound - 1);
 Result mask = Masker<Result>::mask(bound - 1);
 Result num;
 do {
 num = IntConversion<Result, Word>::convert(rnd) & mask;
 } while (num > max);
 return num;
 }
 };
 struct ShiftMultiplier {
 static const Result multiplier() {
 Result res = ShiftMultiplier<Result, exp / 2>::multiplier();
 res *= res;
 if ((exp & 1) == 1) res *= static_cast<Result>(2.0);
 return res;
 }
 };
 template <typename Result, int exp>
 struct ShiftMultiplier<Result, exp, false> {
 static const Result multiplier() {
 Result res = ShiftMultiplier<Result, exp / 2>::multiplier();
 res *= res;
 if ((exp & 1) == 1) res *= static_cast<Result>(0.5);
 return res;
 }
 };
 template <typename Result>
 struct ShiftMultiplier<Result, 0, true> {
 static const Result multiplier() {
 return static_cast<Result>(1.0);
 }
 };
 template <typename Result>
 struct ShiftMultiplier<Result, -20, true> {
 static const Result multiplier() {
 return static_cast<Result>(1.0/1048576.0);
 }
 };
 template <typename Result>
 struct ShiftMultiplier<Result, -32, true> {
 static const Result multiplier() {
 return static_cast<Result>(1.0/424967296.0);
 }
 };
 template <typename Result>
 struct ShiftMultiplier<Result, -53, true> {
 static const Result multiplier() {
 return static_cast<Result>(1.0/9007199254740992.0);
 }
 };
 template <typename Result>
 struct ShiftMultiplier<Result, -64, true> {
 static const Result multiplier() {
 return static_cast<Result>(1.0/18446744073709551616.0);
 }
 };
 template <typename Result, int exp>
 struct Shifting {
 return result * ShiftMultiplier<Result, exp>::multiplier();
 }
 };
 template <typename Result, typename Word,
 int rest = std::numeric_limits<Result>::digits, int shift = 0,
 bool last = rest <= std::numeric_limits<Word>::digits>
 struct RealConversion{
 static const int bits = std::numeric_limits<Word>::digits;
 static Result convert(RandomCore<Word>& rnd) {
 return Shifting<Result, - shift - rest>::
 shift(static_cast<Result>(rnd() >> (bits - rest)));
 }
 };
 template <typename Result, typename Word, int rest, int shift>
 struct RealConversion<Result, Word, rest, shift, false> {
 static const int bits = std::numeric_limits<Word>::digits;
 static Result convert(RandomCore<Word>& rnd) {
 return Shifting<Result, - shift - bits>::
 shift(static_cast<Result>(rnd())) +
 template <typename Word>
 struct BoolProducer {
 Word buffer;
 int num;
 BoolProducer() : num(0) {}
 bool convert(RandomCore<Word>& rnd) {
 if (num == 0) {
 buffer = rnd();
 class Random {
 private:
 // Architecture word
 typedef unsigned long Word;
 _random_bits::RandomCore<Word> core;
 _random_bits::BoolProducer<Word> bool_producer;
 public:
 ///\name Initialization
 ///
 /// \brief Constructor with seed
 ///
 /// Constructor with seed. The current number type will be converted
 /// to the architecture word type.
 template <typename Number>
 Random(Number seed) {
 _random_bits::Initializer<Number, Word>::init(core, seed);
 }
 /// \brief Constructor with array seeding
 ///
 /// Constructor with array seeding. The given range should contain
 /// any number type and the numbers will be converted to the
 /// architecture word type.
 template <typename Iterator>
 Random(Iterator begin, Iterator end) {
 typedef typename std::iterator_traits<Iterator>::value_type Number;
 _random_bits::Initializer<Number, Word>::init(core, begin, end);
 }
 /// \brief Copy constructor
 /// \brief Seeding random sequence
 ///
 /// Seeding the random sequence. The current number type will be
 /// converted to the architecture word type.
 template <typename Number>
 void seed(Number seed) {
 _random_bits::Initializer<Number, Word>::init(core, seed);
 }
 /// \brief Seeding random sequence
 ///
 /// Seeding the random sequence. The given range should contain
 /// any number type and the numbers will be converted to the
 /// architecture word type.
 template <typename Iterator>
 void seed(Iterator begin, Iterator end) {
 typedef typename std::iterator_traits<Iterator>::value_type Number;
 _random_bits::Initializer<Number, Word>::init(core, begin, end);
 }
 /// \brief Seeding from file or from process id and time
 if (seedFromFile("/dev/urandom", 0)) return true;
 #endif
 if (seedFromTime()) return true;
 return false;
 }
 /// \brief Seeding from file
 ///
 /// Seeding the random sequence from file. The linux kernel has two
 /// devices, <tt>/dev/random</tt> and <tt>/dev/urandom</tt> which
 /// could give good seed values for pseudo random generators (The
 /// entropy).
 /// \param file The source file
 /// \param offset The offset, from the file read.
 /// \return True when the seeding successes.
 #ifndef WIN32
 bool seedFromFile(const std::string& file = "/dev/urandom", int offset = 0)
 #else
 bool seedFromFile(const std::string& file = "", int offset = 0)
 #endif
 {
 std::ifstream rs(file.c_str());
 const int size = 4;
 Word buf[size];
 ///
 /// Seding from process id and time. This function uses the
 /// current process id and the current time for initialize the
 /// random sequence.
 /// \return Currently always true.
 bool seedFromTime() {
 #ifndef WIN32
 timeval tv;
 gettimeofday(&tv, 0);
 seed(getpid() + tv.tv_sec + tv.tv_usec);
 #else
 /// \brief Returns a random real number the range [0, b)
 ///
 /// It returns a random real number from the range [0, b).
 template <typename Number>
 Number real(Number b) {
 return real<Number>() * b;
 }
 /// \brief Returns a random real number from the range [a, b)
 ///
 /// It returns a random real number from the range [a, b).
 template <typename Number>
 Number real(Number a, Number b) {
 return real<Number>() * (b - a) + a;
 }
 /// @}
 ///\name Uniform distributions
 /// \brief Returns a random real number from the range [0, b)
 ///
 /// It returns a random real number from the range [0, b).
 template <typename Number>
 Number operator()(Number b) {
 return real<Number>() * b;
 }
 /// \brief Returns a random real number from the range [a, b)
 ///
 /// It returns a random real number from the range [a, b).
 template <typename Number>
 Number operator()(Number a, Number b) {
 return real<Number>() * (b - a) + a;
 }
 /// \brief Returns a random integer from a range
 ///
 /// It returns a random integer from the range {0, 1, ..., b - 1}.
 /// It returns a random integer uniformly from the whole range of
 /// the current \c Number type. The default result type of this
 /// function is \c int.
 template <typename Number>
 Number integer() {
 static const int nb = std::numeric_limits<Number>::digits +
 (std::numeric_limits<Number>::is_signed ? 1 : 0);
 return _random_bits::IntConversion<Number, Word, nb>::convert(core);
 }
 int integer() {
 return integer<int>();
 }
 /// \brief Returns a random bool
 ///
 /// It returns a random bool. The generator holds a buffer for
 /// random bits. Every time when it become empty the generator makes
 /// a new random word and fill the buffer up.
 /// @}
 ///\name Non-uniform distributions
 ///
 ///@{
 /// \brief Returns a random bool
 ///
 /// It returns a random bool with given probability of true result.
 bool boolean(double p) {
 return operator()() < p;
 /// Standard Gauss distribution.
 /// \note The Cartesian form of the Box-Muller
 /// transformation is used to generate a random normal distribution.
 /// \todo Consider using the "ziggurat" method instead.
 double gauss()
 {
 double V1,V2,S;
 do {
-	V1=2*real<double>()-1;
+V1=2*real<double>()-1;
-	V2=2*real<double>()-1;
+V2=2*real<double>()-1;
-	S=V1*V1+V2*V2;
+S=V1*V1+V2*V2;
 } while(S>=1);
 return std::sqrt(-2*std::log(S)/S)*V1;
 }
 /// Gauss distribution with given mean and standard deviation
 }
 /// Gamma distribution with given integer shape
 /// This function generates a gamma distribution random number.
 ///
 ///\param k shape parameter (<tt>k>0</tt> integer)
 double gamma(int k)
 {
 double s = 0;
 for(int i=0;i<k;i++) s-=std::log(1.0-real<double>());
 return s;
 }
 /// Gamma distribution with given shape and scale parameter
 /// This function generates a gamma distribution random number.
 ///
 ///\param k shape parameter (<tt>k>0</tt>)
 ///\param theta scale parameter
 ///
 double gamma(double k,double theta=1.0)
 {
 double xi,nu;
 const double delta = k-std::floor(k);
 const double v0=E/(E-delta);
 do {
-	double V0=1.0-real<double>();
+double V0=1.0-real<double>();
-	double V1=1.0-real<double>();
+double V1=1.0-real<double>();
-	double V2=1.0-real<double>();
+double V2=1.0-real<double>();
-	if(V2<=v0)
+if(V2<=v0)
-	  {
+{
-	    xi=std::pow(V1,1.0/delta);
+xi=std::pow(V1,1.0/delta);
-	    nu=V0*std::pow(xi,delta-1.0);
+nu=V0*std::pow(xi,delta-1.0);
-	  }
+}
-	else
+else
-	  {
+{
-	    xi=1.0-std::log(V1);
+xi=1.0-std::log(V1);
-	    nu=V0*std::exp(-xi);
+nu=V0*std::exp(-xi);
-	  }
+}
 } while(nu>std::pow(xi,delta-1.0)*std::exp(-xi));
 return theta*(xi+gamma(int(std::floor(k))));
 }
 /// Weibull distribution
 /// This function generates a Weibull distribution random number.
 ///
 ///\param k shape parameter (<tt>k>0</tt>)
 ///\param lambda scale parameter (<tt>lambda>0</tt>)
 ///
 double weibull(double k,double lambda)
 {
 return lambda*pow(-std::log(1.0-real<double>()),1.0/k);
 }
 /// Pareto distribution
 /// This function generates a Pareto distribution random number.
 ///
 ///\param k shape parameter (<tt>k>0</tt>)
 ///\param x_min location parameter (<tt>x_min>0</tt>)
 ///
 double pareto(double k,double x_min)
 {
 return exponential(gamma(k,1.0/x_min))+x_min;
 }
 /// Poisson distribution
 /// This function generates a Poisson distribution random number with
 /// parameter \c lambda.
 ///
 /// The probability mass function of this distribusion is
 /// \f[ \frac{e^{-\lambda}\lambda^k}{k!} \f]
 /// \note The algorithm is taken from the book of Donald E. Knuth titled
 /// ''Seminumerical Algorithms'' (1969). Its running time is linear in the
 /// return value.
 int poisson(double lambda)
 {
 const double l = std::exp(-lambda);
 int k=0;
 double p = 1.0;
 do {
-	k++;
+k++;
-	p*=real<double>();
+p*=real<double>();
 } while (p>=l);
 return k-1;
 }
 ///@}
 ///\name Two dimensional distributions
 ///
 ///@{
 /// Uniform distribution on the full unit circle
 /// Uniform distribution on the full unit circle.
 ///
 dim2::Point<double> disc()
 {
 double V1,V2;
 do {
-	V1=2*real<double>()-1;
+V1=2*real<double>()-1;
-	V2=2*real<double>()-1;
+V2=2*real<double>()-1;
 } while(V1*V1+V2*V2>=1);
 return dim2::Point<double>(V1,V2);
 }
 /// A kind of two dimensional Gauss distribution
 /// the Box-Muller method.
 dim2::Point<double> gauss2()
 {
 double V1,V2,S;
 do {
-	V1=2*real<double>()-1;
+V1=2*real<double>()-1;
-	V2=2*real<double>()-1;
+V2=2*real<double>()-1;
-	S=V1*V1+V2*V2;
+S=V1*V1+V2*V2;
 } while(S>=1);
 double W=std::sqrt(-2*std::log(S)/S);
 return dim2::Point<double>(W*V1,W*V2);
 }
 /// A kind of two dimensional exponential distribution
 /// This function provides a turning symmetric two-dimensional distribution.
 /// The x-coordinate is of conditionally exponential distribution
 /// with the condition that x is positive and y=0. If x is negative and
 /// y=0 then, -x is of exponential distribution. The same is true for the
 /// y-coordinate.
 dim2::Point<double> exponential2()
 {
 double V1,V2,S;
 do {
-	V1=2*real<double>()-1;
+V1=2*real<double>()-1;
-	V2=2*real<double>()-1;
+V2=2*real<double>()-1;
-	S=V1*V1+V2*V2;
+S=V1*V1+V2*V2;
 } while(S>=1);
 double W=-std::log(S)/S;
 return dim2::Point<double>(W*V1,W*V2);
 }
 ///@}
 };
 extern Random rnd;

changeset 220	a5d8c039f218
parent 178	d2bac07f1742
child 280	e7f8647ce760