Библиотека BOOST C++: генераторы псевдослучайных чисел

English    Главная    Карта    STL    BOOST C++    Loki    Примеры    Метапрограммирование

 

Введение

Synopsis

Шаблон класса random::const_mod

Шаблон класса random::linear_congruential

Класс rand48

Шаблон класса random::additive_combined

Шаблон класса random::shuffle_output

Шаблон класса random::inversive_congruential

Шаблон класса random::mersenne_twister

Шаблон класса random::lagged_fibonacci

Эффективность

Введение

Данная библиотека содержит реализацию нескольких генераторов псевдослучайных чисел. Качество генераторов псевдослучайных чисел очень сильно зависит как от алгоритма, так и от его параметров. Библиотека реализует алгоритмы как шаблоны классов с параметрами. Шаблоны собраны в пространстве имен  boost::random. Любой частный выбор параметров представляется как соответствующим образом объявленные typedef'ы в пространстве имен boost.

Генераторы псевдослучайных чисел не должны создаваться или инициализироваться часто при исполнении программы. Для этого есть две причины. Во-первых, инициализация требует полной установки внутреннего состояния генератора. таким образом, некоторые генераторы со сложной организацией внутреннего состояния дорогостоящи с точки зрения времени. Во-вторых, инициализация всегда требует некоторой величины для задания начального значения генерируемой последовательности чисел. Обычно достаточно трудно получить несколько хороших начальных значений. К примеру, один из методов задания начального значения это определение текущего времени с максимально возможным разрешением. (микро или наносекунды). Когда генератор псевдослучайных чисел инициализируется повторно с использованием текущего времени в качестве затравки, то может случиться, что между инициализациями будет почти постоянный промежуток времени. Этот промежуток может даже быть нулевым, если разрешение системных часов недостаточно. Это приведет к инициализации генератора одним и тем же начальным значением.  Для некоторых приложений это может оказаться неприемлемым.

Заметьте, что все генераторы псевдослучайных чисел, описанные далее, следуют концепциям CopyConstructible and Assignable. Копирование или присваивание генераторов полностью копирует внутреннее состояние генератора, так что исходный генератор и его копия будут производить одинаковую последовательность чисел. Зачастую такое поведение нежелательно. В частности, следует опасаться использовать алгоритмы стандартной библиотеки, такие как  std::generate. Они получают аргумент-функтор по значению, что вызывает копирование случайных чисел генератора.

Следующая таблица дает обзор некоторых характеристик генераторов. Длина цикла является грубой оценкой качества генераторов. Аппроксимация относительной скорости есть мера эффективности, большие значения означают большую скорость генерации чисел.

генератор длина цикла примерные потребности в памяти примерная относительная скорость примечания
minstd_rand 231-2 sizeof(int32_t) 40 -
rand48 248-1 sizeof(uint64_t) 80 -
lrand48 (C library) 248-1 - 20 глобальное состояние
ecuyer1988 approx. 261 2*sizeof(int32_t) 20 -
kreutzer1986 ? 1368*sizeof(uint32_t) 60 -
hellekalek1995 231-1 sizeof(int32_t) 3 хорошая равномерность распределения в нескольких измерениях
mt11213b 211213-1 352*sizeof(uint32_t) 100 хорошая равномерность распределения до 350 измерений
mt199377 219937-1 625*sizeof(uint32_t) 100 хорошая равномерность распределения до 623 измерений
lagged_fibonacci607 approx. 232000 607*sizeof(double) 150 -
lagged_fibonacci1279 approx. 267000 1279*sizeof(double) 150 -
lagged_fibonacci2281 approx. 2120000 2281*sizeof(double) 150 -
lagged_fibonacci3217 approx. 2170000 3217*sizeof(double) 150 -
lagged_fibonacci4423 approx. 2230000 4423*sizeof(double) 150 -
lagged_fibonacci9689 approx. 2510000 9689*sizeof(double) 150 -
lagged_fibonacci19937 approx. 21050000 19937*sizeof(double) 150 -
lagged_fibonacci23209 approx. 21200000 23209*sizeof(double) 140 -
lagged_fibonacci44497 approx. 22300000 44497*sizeof(double) 60 -

Как следует из таблицы, при выборе конкретного генератора следует искать компромисс между качеством, эффективностью и затратами памяти. Множество реализованных в библиотеке генераторов позволяет разработчику приложения выбрать оптимальный для конкретной задач вариант. Кроме того, применение нескольких фундаментально различных генераторов в реализации метода Монте-Карло позволяет улучшить достоверность результатов моделирования.

Если имена генераторов ничего Вам не говорят и Вы не знаете, какой генератор выбрать, то можно порекомендовать генератор  boost::mt19937 для начала: он быстрый и обеспечивает приемлемое качество.

Замечание: эти генераторы не предназначены для использования в приложениях, где требуются недетерминированные случайные числа. См.  описание генератора истинно случайных чисел.

В данном разделе не описываются детально методы, которые уже были описаны в концепции.

Synopsis of the generators available from header <boost/random.hpp>

namespace boost {
  namespace random {
    template<class IntType, IntType m>
    class const_mod;
    template<class IntType, IntType a, IntType c, IntType m, IntType val>
    class linear_congruential;
  }
  class rand48;
  typedef random::linear_congruential< /* ... */ > minstd_rand0;
  typedef random::linear_congruential< /* ... */ > minstd_rand;

  namespace random {
    template<class DataType, int w, int n, int m, int r, DataType a, int u,
        int s, DataType b, int t, DataType c, int l, IntType val>
    class mersenne_twister;
  }
  typedef random::mersenne_twister< /* ... */ > mt11213b;
  typedef random::mersenne_twister< /* ... */ > mt19937;

  namespace random {
    template<class FloatType, unsigned int  p, unsigned int q>
    class lagged_fibonacci;
  }
  typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci607;
  typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci1279;
  typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci2281;
  typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci3217;
  typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci4423;
  typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci9689;
  typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci19937;
  typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci23209;
  typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci44497;  
} // namespace boost

Шаблон класса random::const_mod

Synopsis

template<class IntType, IntType m>
class random::const_mod
{
public:
  template<IntType c>
  static IntType add(IntType x);

  template<IntType a>
  static IntType mult(IntType x);

  template<IntType a, IntType c>
  static IntType mult_add(IntType x);

  static IntType invert(IntType x);
private:
  const_mod();         // don't instantiate
};

Описание

Шаблонный класс const_mod содержит функции, реализующие арифметику вычетов (modular arithmetic) с тщательным обходом переполнений. Все методы статические; объектов класса const_mod<> быть не может.

Параметр шаблона IntType должен обозначать целочисленный тип. Параметр m это модуль.

Замечание: для перемножений по модулю с большими m, есть трюк, позволяющий выполнять быстрые вычисления при соблюдении некоторых условий:

"A more portable FORTRAN random number generator", Linus Schrage, ACM Transactions on Mathematical Software, Vol. 5, No. 2, June 1979, pp. 132-138

Методы класса

template<IntType c> static IntType add(IntType x)

Возвращает: (x+c) mod m 

template<IntType a> static IntType mult(IntType x)

Возвращает: (a*x) mod m 

template<IntType a, IntType c> static IntType
mult_add(IntType x)

Возвращает: (a*x+c) mod m 

static IntType invert(IntType x)

Возвращает: i такое что (a*i) mod m == 1

Предусловие: m - простое число

Шаблон класса random::linear_congruential

Synopsis

#include <boost/random/linear_congruential.hpp>

template<class IntType, IntType a, IntType c, IntType m, IntType val>
class linear_congruential
{
public:
  typedef IntType result_type;
  static const IntType multiplier = a;
  static const IntType increment = c;
  static const IntType modulus = m;
  static const bool has_fixed_range = true;
  static const result_type min_value;
  static const result_type max_value;
  explicit linear_congruential_fixed(IntType x0 = 1);
  // compiler-generated copy constructor and assignment operator are fine
  void seed(IntType x0);
  IntType operator()();
};

typedef random::linear_congruential<long, 16807L, 0, 2147483647L,
     1043618065L> minstd_rand0;
typedef random::linear_congruential<long, 48271L, 0, 2147483647L,
     399268537L> minstd_rand;

Описание

Реализации шаблона linear_congruential моделируют генератор псевдослучайных чисел. Линейный конгруэнтный метод для генерации псевдослучайных чисел описан в:

"Mathematical methods in large-scale computing units", D. H. Lehmer, Proc. 2nd Symposium on Large-Scale Digital Calculating Machines, Harvard University Press, 1951, pp. 141-146

Пусть x(n) описывает последовательность чисел, возвращаемых генератором. Тогда для линейного конгруэнтного генератора x(n+1) := (a * x(n) + c) mod m. Параметрами для генератора являются числа x(0), a, c, m. Шаблонный параметр IntType должен быть целым типом. Он должен быть достаточен для представления величин a, c, and m. Шаблонные параметры a и c должны быть меньше чем m.

Замечание: Качество этого генератор существенным образом зависит от выбора параметров. Пользовательский код должен использовать один из аккуратно преднастроенных генераторов, такой как minstd_rand.

Методы класса

explicit linear_congruential(IntType x0 = 1)

Эффекты: создается генератор типа linear_congruential с x(0) := x0. 

void seed(IntType x0)

Эффекты: изменяется текущее значение генератора на x0.

Специализации

Специализация minstd_rand0 первоначально была предложена в работе

A pseudo-random number generator for the System/360, P.A. Lewis, A.S. Goodman, J.M. Miller, IBM Systems Journal, Vol. 8, No. 2, 1969, pp. 136-146

Этот генератор вместе с minstd_rand прошел тщательную проверку в

"Random Number Generators: Good ones are hard to find", Stephen K. Park and Keith W. Miller, Communications of the ACM, Vol. 31, No. 10, October 1988, pp. 1192-1201

Класс rand48

Synopsis

#include <boost/random/linear_congruential.hpp>

class rand48 
{
public:
  typedef int32_t result_type;
  static const bool has_fixed_range = true;
  static const int32_t min_value = 0;
  static const int32_t max_value = 0x7fffffff;
  
  explicit rand48(int32_t x0 = 1);
  explicit rand48(uint64_t x0);
  // compiler-generated copy ctor and assignment operator are fine
  void seed(int32_t x0);
  void seed(uint64_t x0);
  int32_t operator()();
};

Описание

Класс rand48 является моделью генератора псевдослучайных чисел. Он использует линейный конгруэнтный алгоритм с параметрами a = 0x5DEECE66D, c = 0xB, m = 2**48. Он дает идентичные с lrand48() результаты (при этом стандартная функция lcong48 не вызывается).

Класс доступен только на платформах, где uint64_t является встроенным целым типом, так что инициализация статических полей типа uint64_t возможна.

Конструкторы

rand48(int32_t x0)

Эффекты: создается генератор типа rand48 с начальным состоянием x(0) := (x0 << 16) | 0x330e. 

rand48(uint64_t x0)

Эффекты: создается генератор типа rand48 с начальным состоянием x(0) := x0.

Задание начального состояния

void seed(int32_t x0)

Эффекты: изменяет текущее состояние x(n) генератора на значение (x0 << 16) | 0x330e. 

void seed(uint64_t x0)

Эффекты: изменяет текущее состояние x(n) генератора на x0.

Шаблон класса random::additive_combine

Synopsis

#include <boost/random/additive_combine.hpp>

template<class MLCG1, class MLCG2, typename MLCG1::result_type val>
class random::additive_combine
{
public:
  typedef MLCG1 first_base;
  typedef MLCG2 second_base;
  typedef typename MLCG1::result_type result_type;
  static const bool has_fixed_range = true;
  static const result_type min_value = 1;
  static const result_type max_value = MLCG1::max_value-1;
  additive_combine();
  additive_combine(typename MLCG1::result_type seed1, 
		   typename MLCG2::result_type seed2);
  result_type operator()();
  bool validation(result_type x) const;
};

typedef random::additive_combine<
    random::linear_congruential<int32_t, 40014, 0, 2147483563, 0>,
    random::linear_congruential<int32_t, 40692, 0, 2147483399, 0>,
  /* unknown */ 0> ecuyer1988;

Описание

Класс additive_combine является моделью генератора псевдослучайных чисел. Он объединяет два мультипликативных линейных конгруэнтных генератора, то есть c = 0. Алгоритм описан в:

"Efficient and Portable Combined Random Number Generators", Pierre L'Ecuyer, Communications of the ACM, Vol. 31, No. 6, June 1988, pp. 742-749, 774

Шаблонные параметры MLCG1 и MLCG2 должны быть двумя разными линейными конгруентными генераторами, каждый с параметром c=0. Каждвый вызов возвращает случайное число X(n) := (MLCG1(n) - MLCG2(n)) mod (m1 - 1), где m1 обозначает модуль MLCG1.

Шаблонный параметр val это проверочное значение, которое проверяется методом validation.

Методы класса

additive_combine()

Эффекты: создается генератор типа additive_combine с использованием конструкторов по умолчанию двух базовых генераторов. 

additive_combine(typename MLCG1::result_type seed1, 
 		 typename MLCG2::result_type seed2)

Effects: создается генератор типа additive_combine, с использованием двух начальных значений для инициализации базовых генераторов.

Специализации

Специализация ecuyer1988 была предложена в вышеупомянутой работе.

Шаблон класса random::shuffle_output

Synopsis

#include <boost/random/shuffle_output.hpp>

template<class UniformRandomNumberGenerator, int k, 
  typename UniformRandomNumberGenerator::result_type val = 0>
class random::shuffle_output
{
public:
  typedef UniformRandomNumberGenerator base_type;
  typedef typename base_type::result_type result_type;
  static const bool has_fixed_range = false;

  shuffle_output();
  template<class T> explicit shuffle_output(T seed);
  explicit shuffle_output(const base_type & rng);
  template<class T> void seed(T s);

  result_type operator()();
  result_type min() const;
  result_type max() const;
  bool validation(result_type) const;
};

Описание

Класс shuffle_output является моделью генератора псевдослучайных чисел. Он перемешивает выход некоторого (обычно линейного конгруэнтного) генератора равномерно распределенных чисел для получения лучших статистических результатов. Согласно Дональду Кнуту (Donald E. Knuth), "The Art of Computer Programming, Vol. 2", алгоритм описан в работе

"Improving a poor random number generator", Carter Bays and S.D. Durham, ACM Transactions on Mathematical Software, Vol. 2, 1979, pp. 59-64.

Выход генератора записывается в буфер длиной k. Каждый результат вызова генератора X(n) используется еще вторым способом: он дает индекс в буфере, откуда извлекается очередное случайное число. Использованный элемент буфера заменяется на результат вызова базового генератора.

Шаблонными параметрами являются базовый генератор и длина буфера k, которая должна быть около 100. Шаблонный параметр val используется для валидации генератора в методе validation.

Методы класса

shuffle_output()

Эффекты: создается генератор типа shuffle_output путем вызова конструктора по умолчанию для базового генератора.

Сложность: Точно k+1 вызовов базового генератора. 

template<class T> explicit shuffle_output(T seed)

Effects: создается генератор типа shuffle_output путем вызова конструктора с одним аргументом для базового генератора.

Сложность: точно k+1 вызовов базового генератора. 

explicit shuffle_output(const base_type & rng)

Предусловие: шаблонный параметр UniformRandomNumberGenerator должен быть типом, соответствующим концепции CopyConstructible.

Эффекты: создается генератор типа shuffle_output на основе копии указанного генератора.

Сложность: точно k+1 вызовов базового генератора. 

template<class T> void seed(T s)

Эффекты: вызывает метод seed с одним аргументом для базового генератора и переинициализирует буфер.

Сложность: точно k+1 вызовов базового генератора.

Специализации

Согласно Гэрри Эрвину (Harry Erwin), специализация kreutzer1986 была предложена в работе:

"System Simulation: programming Styles and Languages (International Computer Science Series)", Wolfgang Kreutzer, Addison-Wesley, December 1986.

Шаблон класса random::inversive_congruential

Synopsis

##include <boost/random/inversive_congruential.hpp>

template<class IntType, IntType a, IntType b, IntType p>
class random::inversive_congruential
{
public:
  typedef IntType result_type;
  static const bool has_fixed_range = true;
  static const result_type min_value = (b == 0 ? 1 : 0);
  static const result_type max_value = p-1;
  static const result_type multiplier = a;
  static const result_type increment = b;
  static const result_type modulus = p;
  explicit inversive_congruential(IntType y0 = 1);
  void seed(IntType y0);
  IntType operator()();
};

typedef random::inversive_congruential<int32_t, 9102, 2147483647-36884165, 2147483647> hellekalek1995;

Описание

Класс inversive_congruential является моделью генератора псевдослучайных чисел. Он использует обратимый (inversive) конгруэнтный алгоритм (ICG), описанный в

";Inversive pseudorandom number generators: concepts, results and links", Peter Hellekalek, In: "Proceedings of the 1995 Winter Simulation Conference", C. Alexopoulos, K. Kang, W.R. Lilegdon, and D. Goldsman (editors), 1995, pp. 255-262. ftp://random.mat.sbg.ac.at/pub/data/wsc95.ps

Выходная последовательность определяется формулой x(n+1) = (a*inv(x(n)) - b) (mod p), где x(0), a, b, и простое число p являются параметрами генератора. Выражение inv(k) обозначает обратное произведение (? - multiplicative inverse) k на множестве целых чисел p, с inv(0) := 0.

Параметр шаблона IntType должен обозначать знаковый целый тип, достаточный для хранения p; a, b, и p являются параметрами генератора.

Замечание: текущая реализация использует алгоритм Евклида для вычисления обратного произведения (? -  the multiplicative inverse). Таким образом, инверсивные генераторы примерно в 10-20 раз медленнее, чем другие генераторы (см. раздел производительность). Однако, в вышеупомянутой работе упоминается только о трехкратном замедлении, так что алгоритм Евклида вероятно не является оптимальным для вычисления обратного произведения (multiplicative inverse).

Методы класса

inversive_congruential(IntType y0 = 1)

Эффекты: создается генератор типа inversive_congruential с начальным состоянием y00. 

void seed(IntType y0)

Эффекты: изменяет текущее состояние генератора на y0.

Специализация

Специализация hellekalek1995 была предложена в вышеупомянутой работе.

Шаблон класса random::mersenne_twister

Synopsis

#include <boost/random/mersenne_twister.hpp>

template<class DataType, int w, int n, int m, int r, DataType a, int u,
int s, DataType b, int t, DataType c, int l, IntType val>
class random::mersenne_twister
{
public:
  typedef DataType result_type;
  static const bool has_fixed_range = true;
  static const result_type min_value;
  static const result_type max_value;
  mersenne_twister();
  explicit mersenne_twister(DataType value);
  template<class Generator> explicit mersenne_twister(Generator & gen);
  // compiler-generated copy ctor and assignment operator are fine
  void seed();
  void seed(DataType value);
  template<class Generator> void seed(Generator & gen);
  result_type operator()();
  bool validation(result_type) const;
};

typedef mersenne_twister<uint32_t,351,175,19,0xccab8ee7,11,7,0x31b6ab00,15,0xffe50000,17, /* unknown */ 0> mt11213b;
typedef mersenne_twister<uint32_t,624,397,31,0x9908b0df,11,7,0x9d2c5680,15,0xefc60000,18, 3346425566U> mt19937;

Описание

Класс mersenne_twister является моделью генератора псевдослучайных чисел. Он использует алгоритм, описанный в:

"Mersenne Twister: A 623-dimensionally equidistributed uniform pseudo-random number generator", Makoto Matsumoto and Takuji Nishimura, ACM Transactions on Modeling and Computer Simulation: Special Issue on Uniform Random Number Generation, Vol. 8, No. 1, January 1998, pp. 3-30. http://www.math.keio.ac.jp/matumoto/emt.html

Замечание: реализованный в Boost.Random вариант был разработан полностью с нуля и не использует генератор mt19937.c опубликованный на вышеупомянутом сайте. Однако, верификация подтвердила, что оба эти генератора дают идентичный результат.

Качество генератора очень критично к выбору его параметров. Пользовательский код должен использовать специально подобранные наборы параметров, например mt19937.

Генератор требует значительное количество памяти для хранения вектора состоярия. К примеру, mt11213b требует примерно 1408 байтов и mt19937 требует около 2496 байтов.

Конструкторы

mersenne_twister()

Эффекты: создается генератор типа mersenne_twister вызывается метод инициализации seed(). 

explicit mersenne_twister(result_type value)

Эффекты: создается генератор типа mersenne_twister и вызывается метод инициализации seed(value). 

template<class Generator> explicit mersenne_twister(Generator & gen)

Эффекты: создается генератор типа mersenne_twister и вызывается метод инициализации seed(gen).

Замечание: когда используется синтаксис прямой инициализации через lvalue (к примеру, в виде определения переменной Gen gen2(gen);), данный конструктор шаблона используется вместо сгенерированного компилятором конструктора копирования. Для определения переменной, которая должна скопировать состояние другого генератора типа mersenne_twister, следует использовать Gen gen2 = gen;, где используется синтаксис инициализации-через-копирование и гарантируется, что вызывается конструктор копирования.

Задание начального состояния

void seed()

Эффекты: вызывается метод seed(result_type(4357)). 

void seed(result_type value)

Эффекты: создается генератор типа linear_congruential<uint32_t, 69069, 0, 0, 0> с аргументом конструктора value и вызывается seed с этим генератором. 

template<class Generator> void seed(Generator & gen)

Эффекты: устанавливается состояние генератора в n значений, возвращаемых генератором gen.

Сложность: точно n вызовов генератора gen.

Замечание: когда вызывается метод seed с аргументом в виде lvalue, выбирается метод в шаблоне вне зависимости от типа, который точно соответствует типу  result_type. Для других целых типов необходимо явно преобразовывать аргумент к типу result_type explicitly.

Специализации

Специализации mt11213b и mt19937 описаны в вышеупомянутой работе.

Шаблон класса random::lagged_fibonacci

Synopsis

#include <boost/random/lagged_fibonacci.hpp>

template<class FloatType, unsigned int p, unsigned int q>
class lagged_fibonacci
{
public:
  typedef FloatType result_type;
  static const bool has_fixed_range = false;
  static const unsigned int long_lag = p;
  static const unsigned int short_lag = q;
  result_type min() const { return 0.0; }
  result_type max() const { return 1.0; }
  lagged_fibonacci();
  explicit lagged_fibonacci(uint32_t value);
  template<class Generator>
  explicit lagged_fibonacci(Generator & gen);
  // compiler-generated copy ctor and assignment operator are fine
  void seed(uint32_t value = 331u);
  template<class Generator> void seed(Generator & gen);
  result_type operator()();
  bool validation(result_type x) const;
};

typedef random::lagged_fibonacci<double, 607, 273> lagged_fibonacci607;
typedef random::lagged_fibonacci<double, 1279, 418> lagged_fibonacci1279;
typedef random::lagged_fibonacci<double, 2281, 1252> lagged_fibonacci2281;
typedef random::lagged_fibonacci<double, 3217, 576> lagged_fibonacci3217;
typedef random::lagged_fibonacci<double, 4423, 2098> lagged_fibonacci4423;
typedef random::lagged_fibonacci<double, 9689, 5502> lagged_fibonacci9689;
typedef random::lagged_fibonacci<double, 19937, 9842> lagged_fibonacci19937;
typedef random::lagged_fibonacci<double, 23209, 13470> lagged_fibonacci23209;
typedef random::lagged_fibonacci<double, 44497, 21034> lagged_fibonacci44497;

Описание

Класс lagged_fibonacci является моделью генератора псевдослучайных чисел. Он основан на алгоритме Фибоначчи с параметрами запаздывания p и q, вычисляемыми в арифметике с плавающей точкой: x(i) = x(i-p) + x(i-q) (mod 1) with p > q. См. работу

"Uniform random number generators for supercomputers", Richard Brent, Proc. of Fifth Australian Supercomputer Conference, Melbourne, Dec. 1992, pp. 704-706.

Замечание: качество генератора очень критично к выбору параметров. Пользовательский код должен использовать одну из специально созданных специализаций, такую как lagged_fibonacci607

Генератор требует значительный объем памяти под хранение вектора состояния. К примеру, генератор lagged_fibonacci607 требует примерно 4856 байтов и lagged_fibonacci44497 требует примерно 350 Кб.

Конструкторы

lagged_fibonacci()

Эффекты: создается генератор типа lagged_fibonacci и вызывается метод seed(). 

explicit lagged_fibonacci(uint32_t value)

Эффекты: создается генератор типа lagged_fibonacci и вызывается seed(value). 

template<class Generator> explicit lagged_fibonacci(Generator & gen)

Эффекты: создается генератор типа lagged_fibonacci и вызывается seed(gen).

Задание начального значения

void seed()

Эффекты: вызывается метод seed(331u). 

void seed(uint32_t value)

Эффекты: создается генератор типа minstd_rand0 с аргументом конструктора value и вызывается метод seed. 

template<class Generator> void seed(Generator & gen)

Эффекты: устанавливает состояние генератора lagged_fibonacci в величины, возвращаемые p вызовами распределения uniform_01<gen, FloatType>.

Сложность: точно p вызовов gen.

Специализации

Специализации lagged_fibonacci607 ... lagged_fibonacci44497 (см. выше) используют хорошо проверенные параметры запаздывания. (Ссылки будут добавлены позднее)

Эффективность

Тестовая программа random_speed.cpp измеряет время выполнения реализованных в random.hpp вариантов алгоритмов генерации псевдослучайных чисел в простом цикле (tight loop). Производительность оценивалась на машине Pentium Pro 200 MHz с gcc 2.95.2, Linux 2.2.13, glibc 2.1.2.

класс время одного вызова [мксек]
rand480.096
rand48 run-time configurable 0.697
lrand48 glibc 2.1.20.844
minstd_rand0.174
ecuyer19880.445
kreutzer19860.249
hellekalek1995 (inversive)4.895
mt11213b0.165
mt199370.165
mt19937 original0.185
lagged_fibonacci6070.111
lagged_fibonacci44230.112
lagged_fibonacci199370.113
lagged_fibonacci232090.122
lagged_fibonacci444970.263

Погрешность измерения времени составляет примерно +/- 10 nsec.

Jens Maurer, 2001-08-31
Последняя правка: 09.05.2005

библиотека BOOST C++ http://www.boost.org
перевод Elijah Koziev www.solarix.ru

  © Mental Computing 2010