Subject: [Boost-commit] svn:boost r81001 - trunk/boost/random
From: steven_at_[hidden]
Date: 2012-10-16 17:33:17
Author: steven_watanabe
Date: 2012-10-16 17:33:16 EDT (Tue, 16 Oct 2012)
New Revision: 81001
URL: http://svn.boost.org/trac/boost/changeset/81001
Log:
Make sure that equivalent states of mersenne_twister have identical bits. Fixes #6801.
Text files modified:
trunk/boost/random/mersenne_twister.hpp | 47 ++++++++++++++++++++++++++++-----------
1 files changed, 33 insertions(+), 14 deletions(-)
Modified: trunk/boost/random/mersenne_twister.hpp
==============================================================================
--- trunk/boost/random/mersenne_twister.hpp (original)
+++ trunk/boost/random/mersenne_twister.hpp 2012-10-16 17:33:16 EDT (Tue, 16 Oct 2012)
@@ -147,6 +147,8 @@
// Vol. 2, 3rd ed., page 106
x[i] = (f * (x[i-1] ^ (x[i-1] >> (w-2))) + i) & mask;
}
+
+ normalize_state();
}
/**
@@ -157,13 +159,7 @@
detail::seed_array_int<w>(seq, x);
i = n;
- // fix up the state if it's all zeroes.
- if((x[0] & (~static_cast<UIntType>(0) << r)) == 0) {
- for(std::size_t j = 1; j < n; ++j) {
- if(x[j] != 0) return;
- }
- x[0] = static_cast<UIntType>(1) << (w-1);
- }
+ normalize_state();
}
/** Sets the state of the generator using values from an iterator range. */
@@ -173,13 +169,7 @@
detail::fill_array_int<w>(first, last, x);
i = n;
- // fix up the state if it's all zeroes.
- if((x[0] & (~static_cast<UIntType>(0) << r)) == 0) {
- for(std::size_t j = 1; j < n; ++j) {
- if(x[j] != 0) return;
- }
- x[0] = static_cast<UIntType>(1) << (w-1);
- }
+ normalize_state();
}
/** Returns the smallest value that the generator can produce. */
@@ -333,6 +323,35 @@
}
/**
+ * Converts an arbitrary array into a valid generator state.
+ * First we normalize x[0], so that it contains the same
+ * value we would get by running the generator forwards
+ * and then in reverse. (The low order r bits are redundant).
+ * Then, if the state consists of all zeros, we set the
+ * high order bit of x[0] to 1. This function only needs to
+ * be called by seed, since the state transform preserves
+ * this relationship.
+ */
+ void normalize_state()
+ {
+ const UIntType upper_mask = (~static_cast<UIntType>(0)) << r;
+ const UIntType lower_mask = ~upper_mask;
+ UIntType y0 = x[m-1] ^ x[n-1];
+ if(y0 & (static_cast<UIntType>(1) << (w-1))) {
+ y0 = ((y0 ^ a) << 1) | 1;
+ } else {
+ y0 = y0 << 1;
+ }
+ x[0] = (x[0] & upper_mask) | (y0 & lower_mask);
+
+ // fix up the state if it's all zeroes.
+ for(std::size_t j = 0; j < n; ++j) {
+ if(x[j] != 0) return;
+ }
+ x[0] = static_cast<UIntType>(1) << (w-1);
+ }
+
+ /**
* Given a pointer to the last element of the rewind array,
* and the current size of the rewind array, finds an element
* relative to the next available slot in the rewind array.