Как создать огромное количество высококачественных случайных чисел?
Я работаю над моделированием случайного блуждания частиц, движущихся в решетке. По этой причине я должен создать огромное количество случайных чисел, около 10 ^ 12 и выше. В настоящее время я использую возможности, предоставляемые C ++ 11 <random>, При профилировании моей программы я вижу, что большая часть времени уходит на <random>, Подавляющее большинство этих чисел находятся в диапазоне от 0 до 1, распределены равномерно. Вот тогда мне нужен номер из биномиального распределения. Но основное внимание уделяется цифрам 0..1.
Вопрос заключается в следующем: что я могу сделать, чтобы сократить время процессора, необходимое для генерации этих чисел, и как это повлияет на их качество?
Как видите, я пробовал разные движки, но это не сильно повлияло на процессорное время. Далее, в чем разница между моими uniform01(gen) а также generate_canonical<double,numeric_limits<double>::digits>(gen) во всяком случае?
Редактировать: Читая ответы, я делаю вывод, что не существует идеального решения для моей проблемы. Таким образом, я решил сначала сделать мою программу способной к многопоточности и запускать несколько ГСЧ в разных потоках (посеянных с помощью одного номера random_device + отдельного приращения потока). На данный момент этот шов будет самым неизбежным шагом (многопоточность потребуется в любом случае). В качестве дальнейшего шага, в ожидании точных требований, я рассматриваю переход на предложенный Intel RNG или Thrust. Это означает, что моя реализация RNG не должна быть сложной, чего в настоящее время нет. Но сейчас я хотел бы сосредоточиться на физической корректности моей модели, а не на программировании, это происходит, как только результаты моей программы физически верны.
осевая нагрузка
По поводу Intel RNG
Вот что я делаю сейчас:
class Generator {
public:
Generator();
virtual ~Generator();
double rand01(); //random number [0,1)
int binomial(int n, double p); //binomial distribution with n samples with probability p
private:
std::random_device randev; //seed
/*Engines*/
std::mt19937_64 gen;
//std::mt19937 gen;
//std::default_random_engine gen;
/*Distributions*/
std::uniform_real_distribution<double> uniform01;
std::binomial_distribution<> binomialdist;
};
Generator::Generator() : randev(), gen(randev()), uniform01(0.,1.), binomial(1,1.) {
}
Generator::~Generator() { }
double Generator::rand01() {
//return uniform01(gen);
return generate_canonical<double,numeric_limits<double>::digits>(gen);
}
int Generator::binomialdist(int n, double p) {
binomial.param(binomial_distribution<>::param_type(n,p));
return binomial(gen);
}
Решение
Вы можете предварительно обработать случайные числа и использовать их, когда вам нужно.
Если вам нужны настоящие случайные числа, я предлагаю вам воспользоваться такой услугой, как http://www.random.org/ это обеспечивает случайные числа, рассчитанные по окружающей среде, а не какой-то алгоритм.
И, говоря о случайных числах, вы также должны проверить это:
Другие решения
Если вам нужно огромное количество случайных чисел, а я имею в виду MASSIVE, сделайте тщательный поиск в интернете генератора случайных чисел IBM с плавающей запятой, опубликованного, может быть, десять лет назад. Вам придется купить либо машину PowerPC, либо более новую машину Intel с плавным многократным добавлением. Они достигли случайных чисел со скоростью один за цикл на ядро. Так что, если вы купили новый Mac Pro, вы могли бы достичь 50 миллиардов случайных чисел в секунду.
Возможно, вместо использования процессора вы могли бы использовать графический процессор для одновременного генерирования большого числа чисел?
http://http.developer.nvidia.com/GPUGems3/gpugems3_ch37.html
На моем i3 следующая программа запускается примерно через пять секунд:
#include <random>
std::mt19937_64 foo;
double drand() {
union {
double d;
long long l;
} x;
x.d = 1.0;
x.l |= foo() & (1LL<<53)-1;
return x.d-1;
}
int main() {
double d;
for (int i = 0; i < 1e9; i++)
d += drand();
printf("%g\n", d);
}
в то время как замена drand() вызовите со следующими результатами в программе, которая выполняется примерно за десять секунд:
double drand2() {
return std::generate_canonical<double,
std::numeric_limits<double>::digits>(foo);
}
Используя следующее вместо drand() также приводит к программе, которая выполняется примерно за десять секунд:
std::uniform_real_distribution<double> uni;
double drand3() {
return uni(foo);
}
Возможно хакер drand() Вышесказанное лучше подходит вашим целям, чем стандартные решения.
Определение задачи
ОП просит получить ответ для обоих
1. Скорость генерации — предполагая набор 10E+012 случайные числа быть «массивный«
а также
2. Качество генератора — со слабым предположением, что числа, просто равномерно распределенные по некоторому диапазону значений, также случайны
Однако для реальной системы необходимо рассмотреть и успешно решить еще несколько кардинальных аспектов:
A. Определите, нужно ли обеспечить симуляцию вашей системы гарантия повторяемости последовательности случайных чисел для будущих повторов эксперимента.
Если это не так, повторы симулированного эксперимента в основном приведут к разные результаты тогда процессу рандомизатора (или пре-рандомизатору и рандомизированному селектору) не нужно беспокоиться об их повторном входе в режим работы с полным состоянием и он получит гораздо более простую реализацию.
B. Определите, до какого уровня вам нужно доказательство качества случайности из сгенерированных случайных чисел (или должны ли сгенерированные наборы случайных чисел принадлежать к какому-то определенному закону теории статистики (некоторые известные синтетические распределения или действительно случайные с максимальной колмогоровской сложностью результирующего набора случайных чисел)). Не нужно быть экспертом АНБ, чтобы утверждать, что числовые генераторы истинно-случайных последовательностей — это очень сложный вопрос, и его вычислительные затраты связаны с производством продуктов с высокой случайностью.
Гипер-хаотические и истинно-случайные последовательности в вычислительном отношении чрезвычайно дороги. Использование генераторов с низкой или плохой случайностью не подходит для приложений, чувствительных к качеству случайности (что бы ни говорили маркетинговые документы, ни одна система с градацией MIL-STD или NSA никогда не будет испытывать это скомпрометированное качество в окружающей среде, где результаты действительно имеют значение Так зачем же соглашаться на меньшее в научных симуляциях? Возможно, это не проблема, если вы не против пропустить так много «не посещаемых» состояний симулируемых явлений).
C. Проверьте, сколько случайных чисел требуется вашей системе моделирования для «потребления на [usec]» и является ли этот параметр требования проекта постоянным или может быть увеличен путем перехода к многопоточным, векторизованным, распределенным вычислениям на основе Grid / Cloud. фреймворк.
D. Требует ли ваша система моделирования поддержки глобального или индивидуального управления доступом для каждого потока или perGrid / CloudNode к пулу случайных чисел в случае векторизованной или основанной на Grid / Cloud вычислительной стратегии.
Подход к решению задачи
Самый быстрый [1] и Лучший [2] Решение с [A] и [B] решено, и варианты для [D] состоит в том, чтобы предварительно сгенерировать предельные числа качества случайности в адекватном пуле доступа (и заплатить приемлемые затраты на [C] и [D] на политики доступа и управления доступом для повторного чтения из пула, а не для повторного генерирования).