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

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

Выходные числа не будут иметь особенно простого шаблона mod 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.

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

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

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

Псевдокод исходной LCG:

function rand
   state := update(state)
   return state

Псевдокод LCG, включая свопинг:

function rand2
   state := update(state) -- unchanged state computation
   return swapped(state)  -- output swapped state

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

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.

Еще один простой, эффективный и хорошо понятный ГПСЧ - это регистр сдвига линейной обратной связи. Полный период легко достичь, выполнив действия, описанные в статье.

РЕДАКТИРОВАТЬ:

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

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

Википедия довольно ясна.

Если вы выберете простой и быстрый 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.

По следующей ссылке вы можете найти пример комбинированного 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