Генерация случайных чисел или перестановок полного периода / полного цикла Аналогично LCG, но без четных / нечетных - PullRequest
Новая
       4

Генерация случайных чисел или перестановок полного периода / полного цикла Аналогично LCG, но без четных / нечетных

8 голосов
/ 27 августа 2010

Я хочу генерировать псевдослучайные числа / перестановки, которые «занимают» полный период или полный цикл в пределах диапазона.Обычно «Линейный конгруэнтный генератор» (LCG) может использоваться для генерации таких последовательностей, используя формулу, такую ​​как: 

X = (a*Xs+c) Mod R

Где Xs - начальное число, X - результат, a и c относительно простые.константы, а R - максимум (диапазон).

(Под полным периодом / полным циклом я подразумеваю, что константы могут быть выбраны так, что любой X будет встречаться только один раз в некоторой случайной / переставленной последовательности и будет в пределахдиапазон от 0 до R-1 или от 1 до R).

LCG почти соответствует всем моим потребностям.Проблема, которую я имею с LCG, заключается в неслучайности нечетного / четного результата, то есть: для начального числа Xn результат X будет чередоваться нечетным / четным.

Вопросы:

  1. Кто-нибудь знает, как создать нечто подобное, которое не будет чередоваться нечетно / четно?

  2. Я считаю, что «Составной LCG» может быть построен,но у меня нет деталей.Кто-нибудь может привести пример этого CLCG?

  3. Существуют ли альтернативные формулы, которые могут соответствовать приведенным выше деталям и ограничениям ниже?

Ограничения:

Я хочу что-то, основанное на простой формуле на основе семян.То есть: чтобы получить следующее число, я предоставляю начальное число и получаю следующее «случайное число» в переставленной последовательности.В частности, я не могу использовать предварительно рассчитанные массивы.(См. Следующие пункты) Последовательность обязательно должна быть «полный период / полный цикл» Диапазон R может составлять несколько миллионов или даже 32 бита / 4 миллиарда.

Расчет не должен быть переполнен и должен быть эффективным / быстрым, то есть: без больших показателей или десятков умножений / делений.

Последовательность не должна быть ужасно случайной или безопасной -Мне не нужна криптографическая случайность (но я могу использовать ее, если она жизнеспособна), просто «хорошая» случайность или кажущаяся случайность, без нечетных / четных последовательностей.

Любые мысли приветствуются - спасибо заранее.

ОБНОВЛЕНИЕ: В идеале переменная Range не может быть точной степенью двойки, но должна работать в любом случае.

Ответы [ 6 ]

9 голосов
/ 10 июня 2011

Тривиальное решение.Сделайте LCG с R простым числом, несколько большим, чем желаемый диапазон, и оба a и c где-то случайные в этом диапазоне.Если он дает вам число, которое больше, чем вы хотите, повторите итерацию до тех пор, пока вы не вернетесь в диапазон.

Вывод чисел не будет иметь особенно простой шаблон мод 2, 3, 5 и т. Д. Вплоть до любого простого числаменьше, чем простое число, которое вы используете.

Если диапазон, который вы хотите, велик, то ближайший больший простор будет лишь на небольшую величину больше, поэтому вам очень редко придется вызывать его дважды.Например, если желаемый диапазон составляет миллиард, вы можете использовать 1000000007 в качестве основного числа, и вам нужно будет пропустить дополнительное число меньше 0,000001% времени.

Я нашел это простое число, перейдя к http://primes.utm.edu/curios/includes/primetest.php и вводить числа, пока я не получу простое число.Мне немного повезло.Шансы на то, что n, оканчивающийся на 1, 3, 7, 9, являются простыми, приблизительно равны 2.5/log(n), что составляет около 12% на миллиард, поэтому мне немного повезло найти это число после всего лишь 4 попыток.Но не повезло - я нашел его за 3 попытки, и в среднем мне нужно было 8.

РЕДАКТИРОВАТЬ: Этот генератор случайных чисел может иметь более короткий цикл.Смотрите заметку @ dzugaru.

3 голосов
/ 27 августа 2010

Если нечетное / четное чередование является вашей единственной проблемой, оставьте вычисление изменения состояния без изменений.Перед использованием каждого выхода вы можете либо сдвинуть младшие биты, либо поменять их местами.

Редактировать:

В варианте с битовой заменой (с фиксированной комбинацией) вы продолжите генерировать целые периоды.

Псевдокод начальной LCG: 

function rand
   state := update(state)
   return state

Псевдокод LCG, включая замену: 

function rand2
   state := update(state) -- unchanged state computation
   return swapped(state)  -- output swapped state
2 голосов
/ 03 марта 2015

Переставленные конгруэнтные генераторы, кажется, обладают всеми качествами, которые вы ищете:

http://www.pcg -random.org 

// *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / pcg-random.org
// Licensed under Apache License 2.0 (NO WARRANTY, etc. see website)

typedef struct { uint64_t state;  uint64_t inc; } pcg32_random_t;

uint32_t pcg32_random_r(pcg32_random_t* rng)
{
    uint64_t oldstate = rng->state;
    // Advance internal state
    rng->state = oldstate * 6364136223846793005ULL + (rng->inc|1);
    // Calculate output function (XSH RR), uses old state for max ILP
    uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u;
    uint32_t rot = oldstate >> 59u;
    return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
}

Существуют и другие вариантыдоступны на веб-сайте, включая реализацию C ++, предназначенную для работы с заголовком <random> (например, дистрибутивы), более полную реализацию C и реализацию Haskell.

2 голосов
/ 16 июня 2011

То, что вам не нужна криптографическая стойкость, не означает, что вы не можете заимствовать некоторые идеи из криптографии ... Как сеть Фейстеля (конструкция Луби-Ракоффа).

Изображение из Википедии довольно четкое.

Если вы выберете простой и быстрый F - ему даже не нужно гарантировать уникальный вывод - тогда вы можете просто передать последовательность (0, 1, 2, ..., 2 ^ n-1) в несколько раундов сети Фейстеля. Поскольку конструкция обратима, это гарантирует, что вывод никогда не повторяется.

Пример кода для 32 бит: 

#include <stdint.h>
#include <stdio.h>

/* Just some fixed "random" bits... */
union magic {
    double d;
    uint16_t n[4];
};

const union magic bits = { 3.141592653589793238462643383 };

static uint16_t
F(uint16_t k, uint16_t x)
{
    return 12345*x + k;
}

static uint32_t
gen_rand(uint32_t n)
{
    uint16_t left = n >> 16;
    uint16_t right = n & ((1UL << 16) - 1);

    for (unsigned round=0 ; round < 4 ; ++round) {
        const uint16_t next_right = left ^ F(bits.n[round], right);
        const uint16_t next_left = right;
        right = next_right;
        left = next_left;
    }

    return (((uint32_t)left) << 16) + right;
}

int
main(int argc, char *argv[])
{
    for (uint32_t n = 0 ; n < 10 ; ++n) {
        printf("gen_rand(%lu) == %08lx\n", (unsigned long)n,
               (unsigned long)gen_rand(n));
    }
    return 0;
}

Вы можете возиться с определением F (), количеством раундов и т. Д. На свой вкус. Свойство «полный цикл» гарантировано независимо от того, что вы там используете. Другими словами, если у вас есть цикл в main, переходящий от 0 до 2 ^ 32-1, каждое 32-разрядное целое число будет встречаться один и только один раз, независимо от того, что вы используете для F или количества раундов.

Это не совсем соответствует вашему заявленному требованию, поскольку входное значение для gen_rand не является "текущим случайным числом" ... Входное значение является просто следующим целым числом. Однако это позволяет вам генерировать любой элемент последовательности по желанию (произвольный доступ). И это легко инвертировать, если вы действительно хотите передать «текущее случайное число» в качестве входных данных.

Довольно легко адаптируется к разному количеству битов, хотя для этого требуется, чтобы ваш R был степенью 2.

2 голосов
/ 27 августа 2010

Еще один простой, эффективный и понятный PRNG - это Линейный регистр сдвига с обратной связью . Полный период легко достичь, следуя инструкциям в статье.

EDIT:

Вы можете рассмотреть некоторые методы, разработанные для Форматно-сохраняющее шифрование . Я считаю, что они могут быть легко адаптированы для создания перестановки.

1 голос
/ 12 декабря 2010

В следующей ссылке вы можете найти пример комбинированного LCG.(Документы и источник включены) (Примечание: алгоритм открыт, но лицензия на источник не открыта (т.е. без производного кода))

http://resource.npl.co.uk/docs/science_technology/scientific_computing/ssfm/documents/wh_rng_version096.zip

Вы можете даже попробовать это7-ступенчатый пример XORshift RNG:

https://gist.github.com/709285

...