random.hh

00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *     Mikael Lagerkvist <lagerkvist@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2005
00008  *     Mikael Lagerkvist, 2005
00009  *
00010  *  Last modified:
00011  *     $Date: 2006-08-04 16:05:34 +0200 (Fri, 04 Aug 2006) $ by $Author: schulte $
00012  *     $Revision: 3514 $
00013  *
00014  *  This file is part of Gecode, the generic constraint
00015  *  development environment:
00016  *     http://www.gecode.org
00017  *
00018  *  See the file "LICENSE" for information on usage and
00019  *  redistribution of this file, and for a
00020  *     DISCLAIMER OF ALL WARRANTIES.
00021  *
00022  */
00023 
00024 #ifndef __GECODE_SUPPORT_RANDOM_HH__
00025 #define __GECODE_SUPPORT_RANDOM_HH__
00026 
00027 #define GECODE_RAND_MAX
00028 
00029 namespace Gecode { namespace Support {
00030 
00041   template<unsigned int m, unsigned int a, unsigned int q, unsigned int r>
00042   class LinearCongruentialGenerator {
00043     int s;
00044     unsigned int next() {
00045       s = a*(s%q) - r*(s/q);
00046       if (s<0) s += m;
00047       int res = s;
00048       if (s==0) s = 1;
00049       return res;
00050     }
00051   public:
00052     // The maximum size of random numbers generated.
00053     const unsigned long rand_max;
00054 
00056     LinearCongruentialGenerator(int _seed = 1)
00057       : rand_max(1UL<<31) {
00058       seed(_seed);
00059     }
00061     void seed(unsigned int _seed) {
00062       s = _seed % m;
00063       if (s == 0) s = 1;
00064     }
00066     unsigned int seed(void) const {
00067       return s;
00068     }
00070     unsigned int operator()(unsigned int n) {
00071       unsigned long x1 = next() & ((1<<16)-1);
00072       unsigned long x2 = next() & ((1<<16)-1);
00073       if (n < 2) return 0;
00074       double d = static_cast<double>(((x1<<16) | x2)%rand_max) / rand_max;
00075       int val = static_cast<int>(n * d);
00076       return (val < static_cast<int>(n)) ? val : (n-1);
00077     }
00078   };
00079 
00080 
00093   typedef LinearCongruentialGenerator<2147483647, 48271, 44488, 3399>
00094   RandomGenerator;
00095 
00096 }}
00097 
00098 #endif /* __GECODE_SUPPORT_RANDOM_HH__ */
00099 
00100 // STATISTICS: support-any