2012-02-10

Свой ГСЧ

Стандартный генератор случайных чисел (ГСЧ) в C++ - функция rand(). Он работает по так-называемому конгруэнтному линейному алгоритму. Для инициализации генератора используется srand(seed).

У этого генератора есть несколько неприятных особенностей.

1. Он более-менее сносно работает, когда в своей программе вы генерируете небольшое количество независимых между собой случайных величин. Но когда с помощью одного и того же датчика генерируется с десяток различных переменных (A, B, C, D, E, F, G, H, I, J), то последовательность псевдослучайных значений, например, переменной A: A1, A2, A3, A4, A5, … уже не будет выглядеть как случайная.

2. Требуется производить инициализацию счетчика с помощью функции srand(seed) в каждом потоке, в котором вызывается rand().

В общем, столкнувшись на практике со странностями работы стандартного ГСЧ, я решил написать свой. Основные требования - скорость работы и возможность обращаться к одному и тому же ГСЧ из разных потоков. И вот, что у меня получилось:

class CRnd
{
  private:
    unsigned long m_iran;
  public:
    void Init(unsigned long seed);
    unsigned long Rand();
}
void CRnd::Init(unsigned long seed)
{
  m_iran = seed;
}
unsigned long CRnd::Rand()
{
  unsigned long old_iran = m_iran;
  unsigned long new_iran, cur_iran;
  for (;;)
  {
    new_iran = 1664525L*old_iran+1013904223L;
    cur_iran = InterlockedCompareExchange((volatile long*)&m_iran, new_iran, old_iran);
    if (cur_iran == old_iran) break;
    old_iran = cur_iran;
  }
  return new_iran;
}

UPD. Множитель a = 1664525 и слагаемое c = 1013904223 были взяты из статьи в вики. На практике, однако, выяснилось, что получаемая последовательность чисел имеет короткий период, поэтому имеет смысл использовать другие параметры:
a = 1103515245, c = 12345, m = 2^31.

unsigned long CRnd::Rand()

{
  unsigned long old_iran = m_iran;
  unsigned long new_iran, cur_iran;
  for (;;)
  {
    new_iran = 1103515245L*old_iran+12345L;
    cur_iran = InterlockedCompareExchange((volatile long*)&m_iran, new_iran, old_iran);
    if (cur_iran == old_iran) break;
    old_iran = cur_iran;
  }
  return ((new_iran >> 16) & 32767L);
}

===

Перепечатка материалов блога разрешается с обязательной ссылкой на blog.coolsoftware.ru

cpp, ГСЧ