Функция смешивания для нецелых 2-х целых интервалов - PullRequest
Новая
       23

Функция смешивания для нецелых 2-х целых интервалов

1 голос
/ 22 марта 2019

Я ищу функцию микширования, которая дает целое число из интервала <0, n) возвращает случайное целое число из того же интервала.Размер интервала n обычно будет составной не степенью 2 числа.Мне нужна функция, чтобы быть один к одному.Он может использовать только O (1) памяти, время O (1) настоятельно рекомендуется.Я не слишком обеспокоен случайностью вывода, но визуально он должен выглядеть достаточно случайным (см. Следующий абзац). </p>

Я хочу использовать эту функцию в качестве шага перетасовки пикселей в рендере в реальном времени, чтобы выбратьпорядок рендеринга пикселей (вывод будет отображаться через фиксированное время, и если это еще не сделано, это дает мне шумный, но быстрый частичный предварительный просмотр).Размер интервала n будет количеством пикселей в рендере (типичным значением будет n = 1920 * 1080 = 2073600).Функция должна быть один к одному, чтобы я мог быть уверен, что каждый пиксель будет отображаться ровно один раз, когда закончите.

Я посмотрел на обратимые строительные блоки, используемые hash prospector , нов основном они зависят от мощности двух диапазонов.

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

Что такоедругие варианты здесь?

1 Ответ

1 голос
/ 27 марта 2019

Вот одно решение, основанное на идее примитивных корней по модулю простого числа:

Если a является модом примитивного корня p, то функция g(i) = a^i % p является перестановкой ненулевых элементов, которыеменьше чем p.Это соответствует Lehmer prng .Если n < p, вы можете получить перестановку 0, ..., n-1 следующим образом: учитывая i в этом диапазоне, сначала добавьте 1, а затем многократно умножьте на a, взяв мод p результата, пока не получите элемент<= n, в этот момент вы возвращаете результат - 1.

Чтобы заполнить детали, этот документ содержит таблицу, которая дает ряд простых чисел (все из которых являютсяблизки к различным степеням 2) и соответствующим примитивным корням, которые выбраны так, что они дают генератор с хорошими статистическими свойствами.Вот часть этой таблицы, закодированная как словарь Python, в которой ключами являются простые числа, а корнями-примитивами являются значения: 

d = {32749: 30805,
     65521: 32236,
     131071: 66284,
     262139: 166972,
     524287: 358899,
     1048573: 444362,
     2097143: 1372180,
     4194301: 1406151,
     8388593: 5169235,
     16777213: 9726917,
     33554393: 32544832,
     67108859: 11526618,
     134217689: 70391260,
     268435399: 150873839,
     536870909: 219118189,
     1073741789: 599290962}

Задано n (в определенном диапазоне - см.бумаги, если вам нужно расширить этот диапазон), вы можете найти наименьшее p, которое работает: 

def find_p_a(n):
    for p in sorted(d.keys()):
        if n < p:
            return p, d[p]

, когда вы знаете n и соответствующий p,a, следующая функция является перестановкой 0 ... n-1: 

def f(i,n,p,a):
    x = a*(i+1) % p
    while x > n:
        x = a*x % p
    return x-1

Для быстрого теста: 

n = 2073600
p,a = find_p_a(n) # p = 2097143, a = 1372180
nums = [f(i,n,p,a) for i in range(n)]
print(len(set(nums)) == n) #prints True

Среднее число умножений в f() равно p/n, которое в данном случае равно 1.011 и будетникогда не превышать 2 (или не намного больше, поскольку p не являются точными степенями 2).На практике этот метод принципиально не отличается от вашего подхода «умножить на большое простое число», но в этом случае фактор выбирается более тщательно, и тот факт, что иногда требуется более 1 умножения, добавляет к кажущейся случайности.

...