Существуют ли линейные алгоритмы конгруэнтного генератора, которые возвращают только положительные значения?
Я знаю об одном; ZX Spectrum, очевидно, использовал RNG Лемера с модулем 65537 и множителем 75. Это генерирует только числа больше нуля. Тем не менее, я хотел бы использовать что-то с периодом более 2^16 - 1.
Я использую это на языке с 32-битной длиной слова для целых чисел (Haxe), поэтому в идеале он должен быть меньше 2^31. Тем не менее, я не обязательно ищу специфичный для Haxe ответ.
2 ответа
На машинах, которые используют дополнение до двух (что означает x86 и производные, и почти на любом другом компьютере, с которым вы можете столкнуться), старший бит используется для обозначения знака. Если старший бит установлен, то число является отрицательным.
Таким образом, вы можете убедиться, что число положительное, очистив старший бит. В случае 32-разрядного числа это просто вопрос:
result = result & 0x7FFFFFFF;
Хорошо, это должно было быть очевидно, но я понял это. Вот мое уравнение:
internalSeed = ( internalSeed * MULTIPLIER + INCREMENT ) % MODULUS + MODULUS;
Чтобы не допустить превышения длины слова для целого числа и, тем не менее, обеспечить большой период возвратов, я использовал псевдослучайные значения Microsoft Visual Basic 6:
MULTIPLIER = 1140671485
INCREMENT = 12820163
MODULUS = 16777216
Тогда + MODULUS значение курса меняет диапазон от ( -16777216, 16777216) до ( 0, 33554429), что я и хотел.
Изменить: некоторые из комментариев выше предлагают различные решения.
На месте Math.abs(), всегда можно запустить простую проверку if ( result < 0 ) и затем умножьте результат на -1, если истина. Я не уверен, насколько это повлияет на скорость, но я не думаю, что это будет сильно.
Самый сложный ответ - побитовое И для результата с 0x7FFFFFFF, чтобы обрезать отрицательный бит. Это не влияет на скорость и действительно обеспечивает положительную ценность.