Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Hive_Milestone3/sources/HeuristicLab.Random/3.2/MersenneTwister.cs @ 4067

Last change on this file since 4067 was 1530, checked in by gkronber, 16 years ago

Moved source files of plugins Hive ... Visualization.Test into version-specific sub-folders. #576

File size: 10.8 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2008 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22/*
23 * C# port of the freeware implementation of the Mersenne Twister
24 * originally developed by M. Matsumoto and T. Nishimura
25 *
26 * M. Matsumoto and T. Nishimura,
27 * "Mersenne Twister: A 623-Dimensionally Equidistributed Uniform
28 * Pseudo-Random Number Generator",
29 * ACM Transactions on Modeling and Computer Simulation,
30 * Vol. 8, No. 1, January 1998, pp 3-30.
31 *
32 */
33
34using System;
35using System.Collections.Generic;
36using System.Text;
37using System.Xml;
38using HeuristicLab.Core;
39
40namespace HeuristicLab.Random {
41  /// <summary>
42  /// A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator.
43  /// </summary>
44  public class MersenneTwister : ItemBase, IRandom {
45    private const int n = 624, m = 397;
46
47    private object locker = new object();
48    private uint[] state = new uint[n];
49    private int p = 0;
50    private bool init = false;
51
52    /// <summary>
53    /// Initializes a new instance of <see cref="MersenneTwister"/>.
54    /// </summary>
55    public MersenneTwister() {
56      if (!init) seed((uint)DateTime.Now.Ticks);
57      init = true;
58    }
59    /// <summary>
60    /// Initializes a new instance of <see cref="MersenneTwister"/>
61    /// with the given seed <paramref name="s"/>.
62    /// </summary>
63    /// <param name="s">The seed with which to initialize the random number generator.</param>
64    public MersenneTwister(uint s) {
65      seed(s);
66      init = true;
67    }
68    /// <summary>
69    /// Initializes a new instance of <see cref="MersenneTwister"/> with the given seed array.
70    /// </summary>
71    /// <param name="array">The seed array with which to initialize the random number generator.</param>
72    public MersenneTwister(uint[] array) {
73      seed(array);
74      init = true;
75    }
76
77    /// <summary>
78    /// Clones the current instance (deep clone).
79    /// </summary>
80    /// <param name="clonedObjects">Dictionary of all already cloned objects. (Needed to avoid cycles.)</param>
81    /// <returns>The cloned object as <see cref="MersenneTwister"/>.</returns>
82    public override object Clone(IDictionary<Guid, object> clonedObjects) {
83      MersenneTwister clone = new MersenneTwister();
84      clonedObjects.Add(Guid, clone);
85      clone.state = (uint[])state.Clone();
86      clone.p = p;
87      clone.init = init;
88      return clone;
89    }
90
91    /// <summary>
92    /// Resets the current random number generator.
93    /// </summary>
94    public void Reset() {
95      lock (locker)
96        seed((uint)DateTime.Now.Ticks);
97    }
98    /// <summary>
99    /// Resets the current random number generator with the given seed <paramref name="s"/>.
100    /// </summary>
101    /// <param name="s">The seed with which to reset the current instance.</param>
102    public void Reset(int s) {
103      lock (locker)
104        seed((uint)s);
105    }
106
107    /// <summary>
108    /// Gets a new random number.
109    /// </summary>
110    /// <returns>A new int random number.</returns>
111    public int Next() {
112      lock (locker) {
113        return (int)(rand_int32() >> 1);
114      }
115    }
116    /// <summary>
117    /// Gets a new random number being smaller than the given <paramref name="maxVal"/>.
118    /// </summary>
119    /// <exception cref="ArgumentException">Thrown when the given maximum value is
120    /// smaller or equal to zero.</exception>
121    /// <param name="maxVal">The maximum value of the generated random number.</param>
122    /// <returns>A new int random number.</returns>
123    public int Next(int maxVal) {
124      lock (locker) {
125        if (maxVal <= 0)
126          throw new ArgumentException("The interval [0, " + maxVal + ") is empty");
127        int limit = (Int32.MaxValue / maxVal) * maxVal;
128        int value = Next();
129        while (value >= limit) value = Next();
130        return value % maxVal;
131      }
132    }
133    /// <summary>
134    /// Gets a new random number being in the given interval <paramref name="minVal"/> and
135    /// <paramref name="maxVal"/>.
136    /// </summary>
137    /// <param name="minVal">The minimum value of the generated random number.</param>
138    /// <param name="maxVal">The maximum value of the generated random number.</param>
139    /// <returns>A new int random number.</returns>
140    public int Next(int minVal, int maxVal) {
141      lock (locker) {
142        if (maxVal <= minVal)
143          throw new ArgumentException("The interval [" + minVal + ", " + maxVal + ") is empty");
144        return Next(maxVal - minVal) + minVal;
145      }
146    }
147    /// <summary>
148    /// Gets a new double random variable.
149    /// </summary>
150    /// <returns></returns>
151    public double NextDouble() {
152      lock (locker) {
153        return rand_double53();
154      }
155    }
156
157    #region Persistence Methods
158    /// <summary>
159    /// Saves the current instance as <see cref="XmlNode"/> in the specified <paramref name="document"/>.
160    /// </summary>
161    /// <remarks>The state(s) are saved as child node with the tag <c>State</c>, each state separaated with
162    /// a semicolon. Also the elements <c>p</c> and the <c>init</c> flag are saved as child nodes with
163    /// tag names <c>P</c> and <c>Init</c> respectively.</remarks>
164    /// <param name="name">The (tag)name of the <see cref="XmlNode"/>.</param>
165    /// <param name="document">The <see cref="XmlDocument"/> where the data is saved.</param>
166    /// <param name="persistedObjects">A dictionary of all already persisted objects. (Needed to avoid cycles.)</param>
167    /// <returns>The saved <see cref="XmlNode"/>.</returns>
168    public override XmlNode GetXmlNode(string name, XmlDocument document, IDictionary<Guid,IStorable> persistedObjects) {
169      XmlNode node = base.GetXmlNode(name, document, persistedObjects);
170
171      StringBuilder builder = new StringBuilder();
172      builder.Append(state[0]);
173      for (int i = 1; i < state.Length; i++) {
174        builder.Append(';');
175        builder.Append(state[i]);
176      }
177      XmlNode stateNode = document.CreateNode(XmlNodeType.Element, "State", null);
178      stateNode.InnerText = builder.ToString();
179      node.AppendChild(stateNode);
180
181      XmlNode pNode = document.CreateNode(XmlNodeType.Element, "P", null);
182      pNode.InnerText = p.ToString();
183      node.AppendChild(pNode);
184
185      XmlNode initNode = document.CreateNode(XmlNodeType.Element, "Init", null);
186      initNode.InnerText = init.ToString();
187      node.AppendChild(initNode);
188
189      return node;
190    }
191    /// <summary>
192    /// Loads the persisted random number generator from the specified <paramref name="node"/>.
193    /// </summary>
194    /// <remarks>The elements of the current instance must be saved in a special way, see
195    /// <see cref="GetXmlNode"/>.</remarks>
196    /// <param name="node">The <see cref="XmlNode"/> where the instance is saved.</param>
197    /// <param name="restoredObjects">The dictionary of all already restored objects. (Needed to avoid cycles.)</param>
198    public override void Populate(XmlNode node, IDictionary<Guid,IStorable> restoredObjects) {
199      base.Populate(node, restoredObjects);
200
201      string stateString = node.SelectSingleNode("State").InnerText;
202      string[] tokens = stateString.Split(';');
203      for (int i = 0; i < tokens.Length; i++)
204        state[i] = uint.Parse(tokens[i]);
205      p = int.Parse(node.SelectSingleNode("P").InnerText);
206      init = bool.Parse(node.SelectSingleNode("Init").InnerText);
207    }
208    #endregion
209
210    #region Seed Methods
211    /// <summary>
212    /// Initializes current instance with random seed.
213    /// </summary>
214    /// <param name="s">A starting seed.</param>
215    public void seed(uint s) {
216      state[0] = s & 0xFFFFFFFFU;
217      for (int i = 1; i < n; ++i) {
218        state[i] = 1812433253U * (state[i - 1] ^ (state[i - 1] >> 30)) + (uint)i;
219        state[i] &= 0xFFFFFFFFU;
220      }
221      p = n;
222    }
223    /// <summary>
224    /// Initializes current instance with random seed.
225    /// </summary>
226    /// <param name="array">A starting seed array.</param>
227    public void seed(uint[] array) {
228      seed(19650218U);
229      int i = 1, j = 0;
230      for (int k = ((n > array.Length) ? n : array.Length); k > 0; --k) {
231        state[i] = (state[i] ^ ((state[i - 1] ^ (state[i - 1] >> 30)) * 1664525U))
232          + array[j] + (uint)j;
233        state[i] &= 0xFFFFFFFFU;
234        ++j;
235        j %= array.Length;
236        if ((++i) == n) { state[0] = state[n - 1]; i = 1; }
237      }
238      for (int k = n - 1; k > 0; --k) {
239        state[i] = (state[i] ^ ((state[i - 1] ^ (state[i - 1] >> 30)) * 1566083941U)) - (uint)i;
240        state[i] &= 0xFFFFFFFFU;
241        if ((++i) == n) { state[0] = state[n - 1]; i = 1; }
242      }
243      state[0] = 0x80000000U;
244      p = n;
245    }
246    #endregion
247
248    #region Random Number Generation Methods
249    private uint rand_int32() {
250      if (p == n) gen_state();
251      uint x = state[p++];
252      x ^= (x >> 11);
253      x ^= (x << 7) & 0x9D2C5680U;
254      x ^= (x << 15) & 0xEFC60000U;
255      return x ^ (x >> 18);
256    }
257    private double rand_double() { // interval [0, 1)
258      return ((double)rand_int32()) * (1.0 / 4294967296.0);
259    }
260    private double rand_double_closed() { // interval [0, 1]
261      return ((double)rand_int32()) * (1.0 / 4294967295.0);
262    }
263    private double rand_double_open() { // interval (0, 1)
264      return (((double)rand_int32()) + 0.5) * (1.0 / 4294967296.0);
265    }
266    private double rand_double53() { // 53 bit resolution, interval [0, 1)
267      return (((double)(rand_int32() >> 5)) * 67108864.0 +
268        ((double)(rand_int32() >> 6))) * (1.0 / 9007199254740992.0);
269    }
270    #endregion
271
272    #region Private Helper Methods
273    private uint twiddle(uint u, uint v) {
274      return (((u & 0x80000000U) | (v & 0x7FFFFFFFU)) >> 1)
275        ^ (((v & 1U) != 0) ? 0x9908B0DFU : 0x0U);
276    }
277    private void gen_state() {
278      for (int i = 0; i < (n - m); ++i)
279        state[i] = state[i + m] ^ twiddle(state[i], state[i + 1]);
280      for (int i = n - m; i < (n - 1); ++i)
281        state[i] = state[i + m - n] ^ twiddle(state[i], state[i + 1]);
282      state[n - 1] = state[m - 1] ^ twiddle(state[n - 1], state[0]);
283      p = 0; // reset position
284    }
285    #endregion
286  }
287}
Note: See TracBrowser for help on using the repository browser.