Почему java.util.Random использует маску?

Question

Упрощенный (т.е. исключая параллелизм) Random.next(int bits) выглядит как

protected int next(int bits) {
    seed = (seed * multiplier + addend) & mask;
    return (int) (seed >>> (48 - bits));
}

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

protected int next(int bits) {
    seed = seed * multiplier + addend;
    return (int) (seed >>> (64 - bits));
}

? Я много читал о случайных числах, но не вижу причин для этого.

Answer 1

Причина в том, что младшие биты имеют тенденцию иметь меньший период (по крайней мере, в алгоритме, который использует Java)

Из Википедия - линейный конгруэнтный генератор :

Как показано выше, LCG не всегда используют все биты в значениях, которые они производят. Реализация Java производит 48 битов с каждой итерации, но возвращает только 32 старших значащих бита из этих значений. Это связано с тем, что биты старшего разряда имеют более длинные периоды, чем биты младшего разряда (см. Ниже). LCG, использующие этот метод, дают гораздо лучшие значения, чем те, которые этого не делают.

редактирование:

после дальнейшего чтения (удобно в Википедии) значения a, c и m должны удовлетворять этим условиям, чтобы иметь полный период:

1. c и m должны быть относительно простыми числами

2. a-1 делится на все простые множители m

3. a-1 кратно 4, если m кратно 4

Единственное, что я могу ясно сказать, все еще доволен, это # ​​3. № 1 и № 2 должны быть проверены, и у меня есть ощущение, что один (или оба) из них не удается.

Answer 2

Из документов в верхней части java.util.Random:

• Алгоритм описан в Искусство компьютерного программирования,
• Том 2 Дональд Кнут в разделе 3.2.1.Это 48-разрядное начальное число,
• линейная конгруэнтная формула.

Таким образом, весь алгоритм предназначен для работы с 48-разрядным начальным числом, а не с 64-разрядным.Я думаю, вы можете обсудить это с мистером Кнутом; p

Answer 3

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

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

Answer 4

From wikipedia (цитата, на которую ссылается цитата, размещенная @ helloworld922):

Еще одна проблема LCG состоит в том, что биты младшего разряда сгенерированной последовательностииметь намного более короткий период, чем последовательность в целом, если m установлен на степень 2. В общем, n-ная младшая цифра в базовом b представлении выходной последовательности, где bk = m для некоторого целого числа k, повторяется ссамое большее период bn.

И, кроме того, он продолжается (мой курсив):

Младшие биты LCG, когда m - степень 2никогда не следует полагаться на какую-либо степень случайности .Действительно, простая замена 2n на член модуля показывает, что биты младшего разряда проходят очень короткие циклы.В частности, любой полный цикл LCG, когда m является степенью 2, будет давать попеременно нечетные и четные результаты.

В конце концов, причина, вероятно, историческая: люди в Sun хотели, чтобы что-то работалонадежно, а формула Кнута дала 32 значащих бита.Обратите внимание, что API java.util.Random говорит следующее (мой курсив):

Если два экземпляра Random создаются с одним и тем же начальным числом и выполняется одна и та же последовательность вызовов методовдля каждого они будут генерировать и возвращать идентичные последовательности чисел. Чтобы гарантировать это свойство, для класса Random указаны конкретные алгоритмы.Реализации Java должны использовать все алгоритмы, показанные здесь для класса Random, для абсолютной переносимости кода Java. Однако подклассам класса Random разрешено использовать другие алгоритмы, если они придерживаются общих контрактов длявсе методы.

Так что мы застряли с ним в качестве эталонной реализации.Однако это не означает, что вы не можете использовать другой генератор (и подкласс Random или создать новый класс):

с той же страницы Википедии:

MMIX от Donald Knuth m= 2 ⁶⁴ a = 6364136223846793005 c = 1442695040888963407

Существует 64-битная формула для вас.

Случайные числа являются хитрыми (как отмечает Кнут) и зависят отесли вам нужно 64-битное число, вам может быть достаточно просто дважды набрать java.util.Random и объединить биты.Если вы действительно заботитесь о статистических свойствах, используйте что-то вроде Mersenne Twister или, если вас волнует утечка / непредсказуемость информации, используйте java.security.SecureRandom.