newran.cpp

这是cdma2000的一个分组调度算法实例

   int k = (int)(nx * px);
   probs[k] = exp(ln_gamma(nx+1) - ln_gamma(k+1) - ln_gamma(nx-k+1)
      + k * log(px) + (nx-k) * log(qx));
   int i;
   int m = (nx >= 40) ? 39 : nx;
   for (i=k+1; i<=m; i++) probs[i]=probs[i-1] * px * (nx-i+1) / qx / i;
   for (i=k-1; i>=0; i--) probs[i]=probs[i+1] * qx * (i+1) / px / (nx-i);
   dg = new DiscreteGen(m + 1, probs);
   if (!dg) ErrorNoSpace();
}

Binomial2::~Binomial2() { delete dg; }

Real Exponential::Density(Real x) const          // Negative exponential
{ return  (x > 40.0 || x < 0.0) ? 0.0 : exp(-x); }

Poisson::Poisson(Real mu)
{
   if (mu <= 8.0) method = new Poisson2(mu);
   else method = new Poisson1(mu);
   if (!method) ErrorNoSpace();
}

Binomial::Binomial(int nx, Real px)
{
   if (nx < 40 || nx * px <= 8.0) method = new Binomial2(nx, px);
   else method = new Binomial1(nx, px);
   if (!method) ErrorNoSpace();
}

NegativeBinomial::NegativeBinomial(Real NX, Real PX)
   : AsymGen(0.0), N(NX), P(PX), Q(1.0 + PX)
{
   p = 1.0 / Q;  ln_q = log(1.0 - p);
   c = N * log(p) - ln_gamma(N);  mode = (N - 1) * P;
   if (mode < 1.0) mode = 0.0;
}

Real NegativeBinomial::Next() { return floor(AsymGen::Next()); }

Real NegativeBinomial::Density(Real x) const
{
   if (x < 0.0) return 0.0;
   Real ix = floor(x);
   Real l = c + ln_gamma(ix + N) - ln_gamma(ix + 1) + ix * ln_q;
   return  (l < -40.0) ? 0.0 : exp(l);
}

Gamma1::Gamma1(Real alphax)                      // constructor (Real=shape)
{ ralpha=1.0/alphax; ln_gam=ln_gamma(alphax+1.0); alpha=alphax; }

Real Gamma1::Density(Real x) const               // density function for
{                                                // transformed gamma
   Real l = - pow(x,ralpha) - ln_gam;
   return  (l < -40.0) ? 0.0 : exp(l);
}

Real Gamma1::Next()                               // transform variable
{ return pow(PosGen::Next(),ralpha); }

Gamma2::Gamma2(Real alphax) : AsymGen(alphax-1.0) // constructor (Real=shape)
{ alpha=alphax; ln_gam=ln_gamma(alpha); }

Real Gamma2::Density(Real x) const                // gamma density function
{
   if (x<=0.0) return 0.0;
   double l = (alpha-1.0)*log(x) - x - ln_gam;
   return  (l < -40.0) ? 0.0 : exp(l);
}

Gamma::Gamma(Real alpha)                         // general gamma generator
{
   if (alpha<1.0) method = new Gamma1(alpha);
   else if (alpha==1.0) method = new Exponential();
   else method = new Gamma2(alpha);
   if (!method)  ErrorNoSpace();
}

DiscreteGen::DiscreteGen(int n1, Real* prob)     // discrete generator
						 // values on 0,...,n1-1
{
   #ifdef MONITOR
      cout << "constructing DiscreteGen\n";
   #endif
   Gen(n1, prob); val=0;
   mean=0.0; var=0.0;
   { for (int i=0; i<n; i++) mean = mean + i*prob[i]; }
   { for (int i=0; i<n; i++) var = var + square(i-mean) * prob[i]; }
}

DiscreteGen::DiscreteGen(int n1, Real* prob, Real* val1)
                                                 // discrete generator
                                                 // values on *val
{
   #ifdef MONITOR
      cout << "constructing DiscreteGen\n";
   #endif
   Gen(n1, prob); val = new Real[n1];
   if (!val)  ErrorNoSpace();
   for (int i=0; i<n1; i++) val[i]=val1[i];
   mean=0.0; var=0.0;
   { for (int i=0; i<n; i++) mean = mean + val[i]*prob[i]; }
   { for (int i=0; i<n; i++) var = var + square(val[i]-mean)*prob[i]; }
}


void DiscreteGen::Gen(int n1, Real* prob)
{
   n=n1;                                         // number of values
   p=new Real[n]; ialt=new int[n];
   if (!p || !ialt)  ErrorNoSpace();
   Real rn = 1.0/n; Real px = 0; int i;
   for (i=0; i<n; i++) { p[i]=0.0; ialt[i]=-1; }
   for (i=0; i<n; i++)
   {
      Real pmin=1.0; Real pmax=-1.0; int jmin=-1; int jmax=-1;
      for (int j=0; j<n; j++)
      {
         if (ialt[j]<0)
         {
            px=prob[j]-p[j];
            if (pmax<=px) { pmax=px; jmax=j; }
            if (pmin>=px) { pmin=px; jmin=j; }
         }
      }
      if ((jmax<0) || (jmin<0)) Throw(Runtime_error("Newran: method fails"));
      ialt[jmin]=jmax; px=rn-pmin; p[jmax]+=px; px*=n; p[jmin]=px;
      if ((px>1.00001)||(px<-.00001))
         Throw(Runtime_error("Newran: probs don't add to 1 (a)"));
   }
   if (px>0.00001) Throw(Runtime_error("Newran: probs don't add to 1 (b)"));
}

DiscreteGen::~DiscreteGen()
{
   delete [] p; delete [] ialt; delete [] val;
   #ifdef MONITOR
      cout << "destructing DiscreteGen\n";
   #endif
}

Real DiscreteGen::Next()                  // Next discrete random variable
{
   int i = (int)(n*Random::Next()); if (Random::Next()<p[i]) i=ialt[i];
   return val ? val[i] : (Real)i;
}

Real ln_gamma(Real xx)
{
   // log gamma function adapted from numerical recipes in C

   if (xx<1.0)                           // Use reflection formula
   {
      double piz = 3.14159265359 * (1.0-xx);
      return log(piz/sin(piz))-ln_gamma(2.0-xx);
   }
   else
   {
      static double cof[6]={76.18009173,-86.50532033,24.01409822,
         -1.231739516,0.120858003e-2,-0.536382e-5};

      double x=xx-1.0; double tmp=x+5.5;
      tmp -= (x+0.5)*log(tmp); double ser=1.0;
      for (int j=0;j<=5;j++) { x += 1.0; ser += cof[j]/x; }
      return -tmp+log(2.50662827465*ser);
   }
}


Real NegatedRandom::Next() { return - rv->Next(); }

ExtReal NegatedRandom::Mean() const { return - rv->Mean(); }

ExtReal NegatedRandom::Variance() const { return rv->Variance(); }

Real ScaledRandom::Next() { return rv->Next() * s; }

ExtReal ScaledRandom::Mean() const { return rv->Mean() * s; }

ExtReal ScaledRandom::Variance() const { return rv->Variance() * (s*s); }

Real ShiftedRandom::Next() { return rv->Next() + s; }

ExtReal ShiftedRandom::Mean() const { return rv->Mean() + s; }

ExtReal ShiftedRandom::Variance() const { return rv->Variance(); }

Real ReverseShiftedRandom::Next() { return s - rv->Next(); }

ExtReal ReverseShiftedRandom::Mean() const { return - rv->Mean() + s; }

ExtReal ReverseShiftedRandom::Variance() const { return rv->Variance(); }

Real ReciprocalRandom::Next() { return s / rv->Next(); }

ExtReal RepeatedRandom::Mean() const { return rv->Mean() * (Real)n; }

ExtReal RepeatedRandom::Variance() const { return rv->Variance() * (Real)n; }

RepeatedRandom& Random::operator()(int n)
{
   RepeatedRandom* r = new RepeatedRandom(*this, n);
   if (!r) ErrorNoSpace(); return *r;
}

NegatedRandom& operator-(Random& rv)
{
   NegatedRandom* r = new NegatedRandom(rv);
   if (!r) ErrorNoSpace(); return *r;
}

ShiftedRandom& operator+(Random& rv, Real s)
{
   ShiftedRandom* r = new ShiftedRandom(rv, s);
   if (!r) ErrorNoSpace(); return *r;
}

ShiftedRandom& operator-(Random& rv, Real s)
{
   ShiftedRandom* r = new ShiftedRandom(rv, -s);
   if (!r) ErrorNoSpace(); return *r;
}

ScaledRandom& operator*(Random& rv, Real s)
{
   ScaledRandom* r = new ScaledRandom(rv, s);
   if (!r) ErrorNoSpace(); return *r;
}

ShiftedRandom& operator+(Real s, Random& rv)
{
   ShiftedRandom* r = new ShiftedRandom(rv, s);
   if (!r) ErrorNoSpace(); return *r;
}

ReverseShiftedRandom& operator-(Real s, Random& rv)
{
   ReverseShiftedRandom* r = new ReverseShiftedRandom(rv, s);
   if (!r) ErrorNoSpace(); return *r;
}

ScaledRandom& operator*(Real s, Random& rv)
{
   ScaledRandom* r = new ScaledRandom(rv, s);
   if (!r) ErrorNoSpace(); return *r;
}

ScaledRandom& operator/(Random& rv, Real s)
{
   ScaledRandom* r = new ScaledRandom(rv, 1.0/s);
   if (!r) ErrorNoSpace(); return *r;
}

ReciprocalRandom& operator/(Real s, Random& rv)
{
   ReciprocalRandom* r = new ReciprocalRandom(rv, s);
   if (!r) ErrorNoSpace(); return *r;
}

AddedRandom& operator+(Random& rv1, Random& rv2)
{
   AddedRandom* r = new AddedRandom(rv1, rv2);
   if (!r) ErrorNoSpace(); return *r;
}

MultipliedRandom& operator*(Random& rv1, Random& rv2)
{
   MultipliedRandom* r = new MultipliedRandom(rv1, rv2);
   if (!r) ErrorNoSpace(); return *r;
}

SubtractedRandom& operator-(Random& rv1, Random& rv2)
{
   SubtractedRandom* r = new SubtractedRandom(rv1, rv2);
   if (!r) ErrorNoSpace(); return *r;
}

DividedRandom& operator/(Random& rv1, Random& rv2)
{
   DividedRandom* r = new DividedRandom(rv1, rv2);
   if (!r) ErrorNoSpace(); return *r;
}

Real AddedRandom::Next() { return rv1->Next() + rv2->Next() ; }

ExtReal AddedRandom::Mean() const { return rv1->Mean() + rv2->Mean() ; }

ExtReal AddedRandom::Variance() const
   { return rv1->Variance() + rv2->Variance() ; }

Real SubtractedRandom::Next() { return rv1->Next() - rv2->Next() ; }

ExtReal SubtractedRandom::Mean() const { return rv1->Mean() - rv2->Mean() ; }

ExtReal SubtractedRandom::Variance() const
   { return rv1->Variance() + rv2->Variance() ; }

Real MultipliedRandom::Next() { return rv1->Next() * rv2->Next() ; }

ExtReal MultipliedRandom::Mean() const { return rv1->Mean() * rv2->Mean() ; }

ExtReal MultipliedRandom::Variance() const
{
   ExtReal e1 = square(rv1->Mean()); ExtReal e2 = square(rv2->Mean());
   ExtReal v1 = rv1->Variance(); ExtReal v2 = rv2->Variance();
   ExtReal r=v1*v2+v1*e2+e1*v2;
   return r;
}

Real DividedRandom::Next() { return rv1->Next() / rv2->Next() ; }

void Random::load(int*,Real*,Random**)
   { Throw(Logic_error("Newran: illegal combination")); }

void SelectedRandom::load(int* i, Real* probs, Random** rvx)
{
   probs[*i]=p; rvx[*i]=rv; (*i)++;
   delete this;
}

Real SelectedRandom::Next()
   { Throw(Logic_error("Newran: Next not defined")); return 0.0; }

Real AddedSelectedRandom::Next()
   { Throw(Logic_error("Newran: Next not defined")); return 0.0; }

Real RepeatedRandom::Next()
   { Real sum=0.0; for (int i=0; i<n; i++) sum+=rv->Next(); return sum; }

MixedRandom::MixedRandom(int nx, Real* probs, Random** rvx)
{
   n = nx;
   rv = new Random*[n]; if (!rv) ErrorNoSpace();
   for (int i=0; i<n; i++) rv[i]=rvx[i];
   Build(probs);
}

MixedRandom::MixedRandom(AddedSelectedRandom& sr)
{
   n = sr.nelems();                       // number of terms;
   Real* probs = new Real[n]; rv = new Random*[n];
   if (!probs || !rv) ErrorNoSpace();
   int i=0; sr.load(&i,probs,rv);
   Build(probs); delete [] probs;
}

void MixedRandom::Build(Real* probs)
{
   int i;
   dg=new DiscreteGen(n,probs);
   if (!dg) ErrorNoSpace();
   mean=0.0; var=0.0;
   for (i=0; i<n; i++) mean = mean + (rv[i])->Mean()*probs[i];
   for (i=0; i<n; i++)
   {
      ExtReal sigsq=(rv[i])->Variance();
      ExtReal mudif=(rv[i])->Mean()-mean;
      var = var + (sigsq+square(mudif))*probs[i];
   }

}

MixedRandom::~MixedRandom()
{
   for (int i=0; i<n; i++) rv[i]->tDelete();
   delete [] rv; delete dg;
}

Real MixedRandom::Next()
   { int i = (int)(dg->Next()); return (rv[i])->Next(); }

int AddedSelectedRandom::nelems() const
   { return rv1->nelems() + rv2->nelems(); }

void AddedSelectedRandom::load(int* i, Real* probs, Random** rvx)
{
   rv1->load(i, probs, rvx); rv2->load(i, probs, rvx);
   delete this;
}

AddedSelectedRandom& operator+(SelectedRandom& rv1,
   SelectedRandom& rv2)
{
   AddedSelectedRandom* r = new AddedSelectedRandom(rv1, rv2);
   if (!r) ErrorNoSpace(); return *r;
}

AddedSelectedRandom& operator+(AddedSelectedRandom& rv1,
   SelectedRandom& rv2)
{
   AddedSelectedRandom* r = new AddedSelectedRandom(rv1, rv2);
   if (!r) ErrorNoSpace(); return *r;
}

AddedSelectedRandom& operator+(SelectedRandom& rv1,
   AddedSelectedRandom& rv2)
{
   AddedSelectedRandom* r = new AddedSelectedRandom(rv1, rv2);
   if (!r) ErrorNoSpace(); return *r;
}

AddedSelectedRandom& operator+(AddedSelectedRandom& rv1,
   AddedSelectedRandom& rv2)
{
   AddedSelectedRandom* r = new AddedSelectedRandom(rv1, rv2);
   if (!r) ErrorNoSpace(); return *r;
}

SelectedRandom& Random::operator()(double p)
{
   SelectedRandom* r = new SelectedRandom(*this, p);
   if (!r) ErrorNoSpace(); return *r;
}




// Identification routines for each class - may not work on all compilers?

char* Random::Name()            { return "Random";           }
char* Uniform::Name()           { return "Uniform";          }
char* Constant::Name()          { return "Constant";         }
char* PosGen::Name()            { return "PosGen";           }
char* SymGen::Name()            { return "SymGen";           }
char* AsymGen::Name()           { return "AsymGen";          }
char* PosGenX::Name()           { return "PosGenX";          }
char* SymGenX::Name()           { return "SymGenX";          }
char* AsymGenX::Name()          { return "AsymGenX";         }
char* Normal::Name()            { return "Normal";           }
char* ChiSq::Name()             { return "ChiSq";            }
char* Cauchy::Name()            { return "Cauchy";           }
char* Exponential::Name()       { return "Exponential";      }
char* Poisson::Name()           { return "Poisson";          }
char* Binomial::Name()          { return "Binomial";         }
char* NegativeBinomial::Name()  { return "NegativeBinomial"; }
char* Gamma::Name()             { return "Gamma";            }
char* Pareto::Name()            { return "Pareto";           }
char* DiscreteGen::Name()       { return "DiscreteGen";      }
char* SumRandom::Name()         { return "SumRandom";        }
char* MixedRandom::Name()       { return "MixedRandom";      }
char* Geometry::Name()          { return "Geometry";         }

// ********************** permutation generator ***************************

void RandomPermutation::Next(int N, int M, int p[], int start)
{
   // N = size of urn; M = number of draws
   if (N < M) Throw(Logic_error("Newran: N < M in RandomPermutation"));
   int i;
   int* q = new int [N];
   if (!q) ErrorNoSpace();
   for (i = 0; i < N; i++) q[i] = start + i;
   for (i = 0; i < M; i++)
   {
      int k = i + (int)(U.Next() * (N - i));       // uniform on i ... N-1
      p[i] = q[k]; q[k] = q[i];                    // swap i and k terms
                                                   // but put i-th term into p
   }
   delete [] q;
}

void RandomCombination::SortAscending(int n, int gm[])
{
   // from numerical recipies in C - Shell sort

   const double aln2i = 1.442695022; const double tiny = 1.0e-5;
   int m = n; int lognb2 = (int)(aln2i * log((double)n) + tiny);
   while (lognb2--)
   {
      m >>= 1;
      for (int j = m; j<n; j++)
      {
         int* gmj = gm+j; int i = j-m; int* gmi = gmj-m; int t = *gmj;
         while (i>=0 && *gmi>t)  { *gmj = *gmi; gmj = gmi; gmi -= m; i -= m; }
         *gmj = t;
      }
   }
}

#ifdef use_namespace
}
#endif