Ответ 1
Следуя за комментарием, я сделал здесь версию с фиксированной точкой алгоритма. Он использует unsigned 4.60 (т.е. В дробной части числа есть 60 бит), что составляет несколько бит, чем вы можете выйти из double:
int rand7fixed() {
static uint64_t a = 0;
static uint64_t width = 7UL<<60;
static const uint64_t intmask = 0xfUL<<60;
while (((a+width)&intmask) != (a&intmask)) {
width /= 6;
a += (rand6()-1)*width;
}
int n = a >> 60;
a &=~intmask;
a *= 7;
width *= 7;
return n+1;
}
Вышеизложенное оказывается примерно на треть быстрее, чем двойная версия в OP (см. результаты тестов и примечания ниже). Я подозреваю, что время-waster - это не арифметика с плавающей запятой, а конверсии от double до int.
Как указывает R.., это не устраняет смещения; он просто уменьшает его. Простым и разумно быстрым несмещенным алгоритмом было бы многократно генерировать два значения rand6() h и l, пока хотя бы одно из них не равно нулю, а затем верните h*6+l % 7:
int rand7_2() {
int hi, lo;
do {
hi = rand6() - 1;
lo = rand6() - 1;
} while (hi + lo);
return (hi * 6 + lo) % 7 + 1;
}
Если вам нужно уменьшить количество вызовов до rand6, вы можете использовать тот факт, что 6 12 составляет чуть больше 7 11 для генерации 11 7-образных роликов за раз. По-прежнему необходимо отказаться от некоторых наборов из 12 6-рулонов для устранения смещения; частота отбрасывающих наборов будет (612−711)/612), или приблизительно 1 в 11, поэтому в среднем вам понадобится около 1,19 6-рулонов на 7-рулон. Вы могли бы добиться большего, используя 25 6-рулонов для создания 23 7-рулонов (1,13 6-рулонов на 7-рулон), но это не совсем подходит для 64-разрядной арифметики, поэтому предельное преимущество при вызовах rand6 было бы разжевываться, выполняя вычисления в 128-битном режиме.
Здесь решение 11/12:
int rand7_12() {
static int avail = 0;
static uint32_t state = 0;
static const uint32_t discard = 7*7*7*7*7*7*7*7*7*7*7; // 7 ** 11
static const int out_per_round = 11;
static const int in_per_round = 12;
if (!avail) {
do {
state = rand6() - 1;
for (int needed = in_per_round - 1; needed; --needed)
state = state * 6 + rand6() - 1;
}
while (state >= discard);
avail = out_per_round;
}
int rv = state % 7;
state /= 7;
--avail;
return rv + 1;
}
В теории вы должны иметь возможность уменьшить отношение к log76, что составляет около 1.086. Например, вы можете сделать это, создав 895 7-рулонов из 972 6-рулонов, отбросив примерно один из 1600 наборов в среднем на 1.087 6-roll/7-roll, но вам понадобится 2513-битная арифметика для удерживайте состояние.
Я тестировал все четыре функции с не очень точным эталоном, который вызывает rand7 700 000 000 раз, а затем печатает гистограмму результатов. Результаты:
User time with
Algorithm User time rand6() calls cycling rand6()
---------- --------- ------------- ---------------
double 32.6 secs 760223193 13.2 secs
fixed 29.4 secs 760223194 7.9 secs
2 for 1 40.2 secs 1440004276
12 for 11 23.7 secs 840670008
Ниже приведенная выше реализация rand6() представляет собой стандартную библиотеку С++ cnnn cncnnn(), использующую mt19937_64 (64-битный Mersenne Twister) в качестве PRNG. Чтобы попытаться получить лучший дескриптор времени, затраченного на стандартную библиотеку, я также провел тест с использованием простого циклического счетчика в качестве генератора псевдослучайных чисел; остальные 13,2 и 7,9 секунды представляют (примерно) время, затрачиваемое на сам алгоритм, из которого можно сказать, что алгоритм с фиксированной точкой примерно на 40% быстрее. (Трудно получить хорошее чтение по алгоритмам объединения, поскольку фиксированная последовательность упрощает предсказание ветвления и уменьшает количество вызовов rand6, но они занимают менее 5 секунд.)
Наконец, гистограммы в случае, если кто-то хочет проверить смещение (также включает в себя прогон с std::uniform_int_distribution(1,7) для справки):
Algorithm 1 2 3 4 5 6 7
--------- --------- --------- --------- --------- --------- --------- ---------
reference 100007522 100002456 100015800 100005923 99972185 100008908 99987206
double 100014597 100005975 99982219 99986299 100004561 100011049 99995300
fixed 100009603 100009639 100034790 99989935 99995502 99981886 99978645
2 for 1 100004476 99997766 99999521 100001382 99992802 100003868 100000185
12 for 11 99988156 100004974 100020070 100001912 99997472 99995015 99992401