random.icc

00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *     Mikael Lagerkvist <lagerkvist@gecode.org>
00006  *
00007  *  Copyright:
00008  *     Christian Schulte, 2005
00009  *     Mikael Lagerkvist, 2005
00010  *
00011  *  Last modified:
00012  *     $Date: 2007-11-08 15:53:26 +0100 (Thu, 08 Nov 2007) $ by $Author: tack $
00013  *     $Revision: 5219 $
00014  *
00015  *  This file is part of Gecode, the generic constraint
00016  *  development environment:
00017  *     http://www.gecode.org
00018  *
00019  *  Permission is hereby granted, free of charge, to any person obtaining
00020  *  a copy of this software and associated documentation files (the
00021  *  "Software"), to deal in the Software without restriction, including
00022  *  without limitation the rights to use, copy, modify, merge, publish,
00023  *  distribute, sublicense, and/or sell copies of the Software, and to
00024  *  permit persons to whom the Software is furnished to do so, subject to
00025  *  the following conditions:
00026  *
00027  *  The above copyright notice and this permission notice shall be
00028  *  included in all copies or substantial portions of the Software.
00029  *
00030  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00031  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00032  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00033  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00034  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00035  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00036  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00037  *
00038  */
00039 
00040 namespace Gecode { namespace Support {
00041 
00049   template<unsigned int m, unsigned int a, unsigned int q, unsigned int r>
00050   class LinearCongruentialGenerator {
00051   private:
00053     static const unsigned int max = 1UL<<31;
00055     unsigned int s;
00057     unsigned int next(void);
00058   public:
00060     void seed(unsigned int _s);
00062     LinearCongruentialGenerator(unsigned int _s = 1);
00064     unsigned int seed(void) const;
00066     unsigned int operator()(unsigned int n);
00067   };
00068 
00069   template<unsigned int m, unsigned int a, unsigned int q, unsigned int r>
00070   forceinline unsigned int 
00071   LinearCongruentialGenerator<m,a,q,r>::next(void) {
00072     s = a*(s%q) - r*(s/q);
00073     unsigned int res = s;
00074     if (s==0) s = 1;
00075     return res;
00076   }
00077   template<unsigned int m, unsigned int a, unsigned int q, unsigned int r>
00078   forceinline void 
00079   LinearCongruentialGenerator<m,a,q,r>::seed(unsigned int _s) {
00080     s = _s % m;
00081     if (s == 0) s = 1;
00082   }
00083   template<unsigned int m, unsigned int a, unsigned int q, unsigned int r>
00084   forceinline 
00085   LinearCongruentialGenerator<m,a,q,r>::
00086   LinearCongruentialGenerator(unsigned int _s) {
00087     seed(_s);
00088   }
00089   template<unsigned int m, unsigned int a, unsigned int q, unsigned int r>
00090   forceinline unsigned int 
00091   LinearCongruentialGenerator<m,a,q,r>::seed(void) const {
00092     return s;
00093   }
00094   template<unsigned int m, unsigned int a, unsigned int q, unsigned int r>
00095   forceinline unsigned int 
00096   LinearCongruentialGenerator<m,a,q,r>::operator()(unsigned int n) {
00097     unsigned int x1 = next() & ((1<<16)-1);
00098     unsigned int x2 = next() & ((1<<16)-1);
00099     if (n < 2) return 0;
00100     double d = static_cast<double>(((x1<<16) | x2) % max) / max;
00101     unsigned int val = static_cast<unsigned int>(n * d);
00102     return (val < n) ? val : (n-1);
00103   }
00104 
00105 
00116   typedef LinearCongruentialGenerator<2147483647, 48271, 44488, 3399>
00117   RandomGenerator;
00118 
00119 }}
00120 
00121 // STATISTICS: support-any