Предсказуемый генератор псевдослучайных чисел

[Old_Maple]

Данная статья посвящена тем, кому необходимо получать предсказуемые псевдослучайные числа одинарной точности (от 0.0 до 0.9999999), как равномерно распределенную функцию, в широком диапазоне значений аргументов от -2147483648 до 2147483647 (знакового целого 32-разрядного числа).
Область применения предсказуемого генератора псевдослучайных чисел (далее ПГПСЧ) достаточно широка в 3D-геймплеях. Допустим, вам необходимо сделать достаточно огромных размеров карту ландшафтов (10000х10000 кв.км). Причем, эта карта должна содержать различные геологические и климатические зоны. Понятно, что держать такую карту в памяти компьютеров достаточно сложно, тем более, если перемещаться по карте скачками. Поэтому ландшафт такой карты должен формироваться «на лету». Но, попадая каждый раз в одни и те же координаты, ваша карта не должна меняться. Вот тут на помощь и приходит ПГПСЧ, который вам выдаст те же случайные величины, что и в предыдущий раз.
ВНИМАНИЕ! Данную функцию ПГПСЧ нельзя использовать в средствах и алгоритмах шифрования данных!
А теперь все по порядку.
Чтобы вам проще было представить работу данной функции, сделаю кое-какие пояснения. Наверное, многим из вас доводилось по фильмам видеть игровые автоматы в казино. Есть там такой замечательный автомат – «однорукий бандит». Принцип его работы достаточно прост. Дергаешь рычаг – и начинают вращаться несколько барабанов с картинками. Если выпадают одинаковые картинки на всех барабанах, то получаешь выигрыш.
В ПГПСЧ в роли «вращающихся барабанов» выступает линейный массив данных из 256 байт, где содержатся значения от 0 до 255. Каждая ячейка массива должна содержать свое индивидуальное натуральное число в диапазоне от 0 до 255 и не повторяться! Но числа в массиве должны располагаться хаотично. Эта процедура делается всего один раз при инициализации программы и затем храниться в памяти постоянно.
А теперь главное. Разница между ПГПСЧ и «одноруким бандитом» заключается в том, что последовательность псевдослучайных чисел («выпадение картинок») должна повторяться и зависеть от количества раз дергания «рычага». Например, если мы в функцию ПГПСЧ предали значение 238910 («дернули рычаг» 238910 раз), то каждый раз передавая в нее это же число, должны на выходе получать одно и то же случайное число («набор картинок», например 0.727394). Считайте, что каждая цифра в случайном числе 0.727394 после плавающей точки - «картинка». Надеюсь, аналогия понятна.
Итак, у меня в ПГПСЧ стоит четыре одинаковых «барабана» (массива байтов со случайно расположенными значениями от 0 до 255). Но данные «барабаны» из значений которых будет потом собираться случайное число вращаются не хаотично, а по определенному закону, так сказать со своим передаточным числом (скоростью вращения). Это передаточное число для каждого «барабана» зависит от выбранного конкретного простого числа (у каждого барабана оно свое. Примечание: простое число делится только на само себя и на единицу.). Для «барабанов», следующих за первым, передаточное число еще зависит и от числа, выбранного предыдущим «барабаном». Из сказанного следует, что скорость вращения только крайнего правого барабана будет постоянной. А передаточные числа остальных будут с каждым новым шагом меняться, но сохраняя при этом порядок этих изменений. Поясню это примером - алгоритмом на VB6:

Код: Выделить всё

Dim RandSeed(0 To 255) As Byte

Public Type LongFromBytes
    Byte0 As Byte
    Byte1 As Byte
    Byte2 As Byte
    Byte3 As Byte
End Type

Public Type Type_Long
     TLong As Long
End Type

Function Random(Number As Long) As Single
   Dim Rand As LongFromBytes, TL As Type_Long
   Dim Ind1 As Byte, Ind2 As Byte, Ind3 As Byte
   
   Rand.Byte0 = RandSeed(Number And &HFF)
   Ind1 = ((Number \ &HEF) * &HEF + Rand.Byte0) And &HFF
   Rand.Byte1 = RandSeed(Ind1)
   Ind2 = ((Number \ &HF1) * &HF1 + Rand.Byte1) And &HFF
   Rand.Byte2 = RandSeed(Ind2)
   Ind3 = ((Number \ &HFB) * &HFB + Rand.Byte2) And &HFF
   Rand.Byte3 = RandSeed(Ind3) And &H7F  '&H7F-избавление от знака
   LSet TL = Rand 'сборка в целое число       
   Random = TL.TLong * 4.65661287307739E-10 '(деление на большое целое число 2147483648 заменяется умножением на инверсное двойной точности 4.65661287307739E-10) 
End Function


Number – любое натуральное число от -2147483648 до 2147483647;
RandSeed() – это массив случайных однобайтовых чисел от 0 до 255, расположенных хаотично;
Rand.Byte0...Rand.Byte3 – это однобайтные числа, выбранные из массива;
Ind1, Ind2, Ind1 – индексы, или так называемые «передаточные числа», где &HEF = 239, &HF1 = 241, &HFB = 251 – простые числа.
Примечание: Изменяя Number во всем диапазоне значений (от -2147483648 до 2147483647) цикл начнет повторяться через 255×239×241×251 = 3 686 623 995 значений.

Для реализации функции ГППСЧ от двух аргументов X и Y необходимо внести дополнения в саму функцию и вместо одного массива RandSeed использовать два RandSeed(0 TO 1, 0 TO 255). Алгоритм представлен ниже:

Код: Выделить всё

Dim RandSeed(0 To 1, 0 To 255) As Byte

Public Type LongFromBytes
    Byte0 As Byte
    Byte1 As Byte
    Byte2 As Byte
    Byte3 As Byte
End Type

Public Type Type_Long
     TLong As Long
End Type

Function Random2D(X As Long, Y As Long) As Double
   
   Dim RandX As LongFromBytes, TLX As Type_Long
   Dim RandY As LongFromBytes, TLY As Type_Long
   Dim Ind1X As Byte, Ind2X As Byte, Ind3X As Byte
   Dim Ind1Y As Byte, Ind2Y As Byte, Ind3Y As Byte
   Dim RandomX As Double, RandomY As Double
   
   RandX.Byte0 = RandSeed(0, X And &HFF)
   Ind1X = ((X \ &HEF) * &HEF + RandX.Byte0) And &HFF
   RandX.Byte1 = RandSeed(0, Ind1X)
   Ind2X = ((X \ &HF1) * &HF1 + RandX.Byte1) And &HFF
   RandX.Byte2 = RandSeed(0, Ind2X)
   Ind3X = ((X \ &HFB) * &HFB + RandX.Byte2) And &HFF
   RandX.Byte3 = RandSeed(0, Ind3X) And &H7F
   LSet TLX = RandX
   RandomX = TLX.TLong * 4.65661287307739E-10

   RandY.Byte0 = RandSeed(1, Y And &HFF)
   Ind1Y = ((Y \ &HEF) * &HEF + RandY.Byte0) And &HFF
   RandY.Byte1 = RandSeed(1, Ind1Y)
   Ind2Y = ((Y \ &HF1) * &HF1 + RandY.Byte1) And &HFF
   RandY.Byte2 = RandSeed(1, Ind2Y)
   Ind3Y = ((Y \ &HFB) * &HFB + RandY.Byte2) And &HFF
   RandY.Byte3 = RandSeed(1, Ind3Y) And &H7F
   LSet TLY = RandY
   RandomY = TLY.TLong * 4.65661287307739E-10
   
   Random2D = RandomY * RandomX + RandomY + RandomX
   Random2D = Random2D - Int(Random2D)
   
End Function

Здесь, как вы заметили, обе координаты X и Y тоже изменяются в диапазоне от 2147483648 до 2147483647, что позволяет создать 2^64-1=1,84E+19 случайных значений, из них только 1.359E+19 не будут повторятся. Такой диапазон значений нам позволит покрыть поверхность Земли площадью 510 млн. кв. км сеткой 5×5 кв. мм!
Для заполнения массива RandSeed случайными значениями можно использовать этот алгоритм:

Код: Выделить всё

Function InitRandom()
  'Инициализация 2-х массивов случайными числами от 0 до 255
  Dim Count As Integer, i As Integer, j As Integer
  For j = 0 To 1
     Count = 0
     Do
       i = Int(256 * Rnd)
       If RandSeed(j, i) = 0 Then
         Count = Count + 1
         RandSeed(j, i) = Count Mod 256
       End If
     Loop While Count < 256
  Next
End Function


Удачи!

[alibek]

Проще использовать хеш-функцию (MD5 или SHA1) для равномерно распределенного псевдослучайного генератора.
А для игровых данных используют скорее фракталы, чем псевдослучайные последовательности.

Что касается критики: алгоритм мне не кажется разумным.
Целочисленное деление и mod это регулярные функции, как ни разбавляй их сложением и делением.
Обычно для самодельных генераторов используют тригонометрические и гиперболические функции.

[Old_Maple]

Целочисленное деление и mod это регулярные функции, как ни разбавляй их сложением и делением.

В данном алгоритме нет сложения и деления, для получения псевдослучайного числа.

[Debugger]

Идея - хорошо, напоминает, как в старых играх для экономии ресурсов использовали таблицы случайных чисел. Для генерации плавных "случайных" ландшафтов используются фракталы с примесью случайных величин, кстати.

Чем этот вариант лучше, чем использование обычного ГСЧ, встроенного в Бейсик? Я могу в любой момент считать или задать его "seed" - волшебную чиселку, которая задаёт последовательность случайных чисел. Хочу получить понравившуюся мне последовательность - использую сид этой последовательности. Хочу остановить генерацию, и продолжить её позже - записываю сид, и при новом запуске восстанавливаю.

Итак, у меня в ПГПСЧ стоит четыре одинаковых «барабана» (массива байтов со случайно расположенными значениями от 0 до 255). Но данные «барабаны» из значений которых будет потом собираться случайное число вращаются не хаотично, а по определенному закону, так сказать со своим передаточным числом (скоростью вращения). Это передаточное число для каждого «барабана» зависит от выбранного конкретного простого числа (у каждого барабана оно свое. Примечание: простое число делится только на само себя и на единицу.). Для «барабанов», следующих за первым, передаточное число еще зависит и от числа, выбранного предыдущим «барабаном». Из сказанного следует, что скорость вращения только крайнего правого барабана будет постоянной. А передаточные числа остальных будут с каждым новым шагом меняться, но сохраняя при этом порядок этих изменений. Поясню это примером - алгоритмом на VB6:

Я бы добавил, что наименьший делитель у скорости вращения с длиной массива должен равняться единице. Иначе какая-то часть барабана окажется неиспользуемой.
Использование значений предыдущих для вычисления скорости последующих барабанов - принципиально не делает алгоритм ни более, ни менее "хорошим", но с этим довеском обеспечить условие с делителем гораздо сложнее.

[Teranas]

Согласен с Debugger, что ГСЧ уже встроен в VB, и, может я не прав, но для больших карт используют буфер на ЖД.
И возникает другая проблема, при таком подходе, перемещение юнитов по карте и областям...

[Old_Maple]

Для генерации плавных "случайных" ландшафтов используются фракталы с примесью случайных величин, кстати.

Чтобы сделать плавный ландшафт можно использовать ПГПСЧ. Небходимо лишь квадраты сглаживать 32х32, 64х64, 128х128... делая все мельче и мельче. Такая рекурсия заметно будет быстрее.

Чем этот вариант лучше, чем использование обычного ГСЧ, встроенного в Бейсик? Я могу в любой момент считать или задать его "seed" - волшебную чиселку, которая задаёт последовательность случайных чисел. Хочу получить понравившуюся мне последовательность - использую сид этой последовательности. Хочу остановить генерацию, и продолжить её позже - записываю сид, и при новом запуске восстанавливаю.

В VB6 функция rtcRandomNext, к сожалению, использует такую формулу

Код: Выделить всё

seed = (&HFFC39EC3 - (seed * &H2BC03)) And &HFFFFFF
Rnd = seed / &H1000000


поэтому о равномерности говорить не приходится. Попробуйте вывести на экран таким способом:

Код: Выделить всё

  For j% = 0 To ScaleHeight - 1
    For i% = 0 To ScaleWidth - 1
       Co& = Co& + 1
       PSet (i%, j%), &HFFFFFF * Rnd(Co&)
    Next
    DoEvents
  Next

Сами увидите.

Я бы добавил, что наименьший делитель у скорости вращения с длиной массива должен равняться единице.

Здесь специально были выбраны простые числа близкие к 255, чтобы период повторения был большим!

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

Это дает равномерное распределение случайных величин.

Согласен с Debugger, что ГСЧ уже встроен в VB, и, может я не прав, но для больших карт используют буфер на ЖД.
И возникает другая проблема, при таком подходе, перемещение юнитов по карте и областям...

Вот чтобы не использовать разного рода буферы, которые отъедают память, именно и используется предсказуемый ГПСЧ, чтобы восстановить все как было.

[Old_Maple]

Как писал уже выше, Майкрософт в VB6, а равно как в VBA.dll и MSVBVM60.dll в функции Rnd (иначе rtcRandomNext; the function Rnd # 593) использует формулу:

Код: Выделить всё

seed = (&HFFC39EC3 - (seed * &H2BC03)) And &HFFFFFF
Rnd = seed / &H1000000

которая не дает хорошей равномерности.
Поэтому, Mikle здесь:
http://bbs.vbstreets.ru/viewtopic.php?f=1&t=17755&p=135910&hilit=RandInit#p135910
предлагает другой вариант:

Код: Выделить всё

Dim Ri As Double

Public Function Rand() As Single
  Ri = 1.314 * Ri + 1.737
  If Ri > 983732.3456 Then Ri = Ri * 0.3141
  Rand = Ri - Int(Ri)
End Function

Public Sub RandInit(r As Single)
  Ri = r
End Sub

[kibernetics]

Mikle здесь:
http://bbs.vbstreets.ru/viewtopic.php?f=1&t=17755&p=135910&hilit=RandInit#p135910
предлагает другой вариант:

Код: Выделить всё

Dim Ri As Double

Public Function Rand() As Single
  Ri = 1.314 * Ri + 1.737
  If Ri > 983732.3456 Then Ri = Ri * 0.3141
  Rand = Ri - Int(Ri)
End Function

Public Sub RandInit(r As Single)
  Ri = r
End Sub

Интересно, зачем тут процедура RandInit? 
Похоже что это эквивалент Randomize. А какое тогда туда значение посылать r?

И ещё такой вопрос, как сымитировать выпадения кубика?
Стандартно это так:

Код: Выделить всё

Int(6 * Rnd()+1)

а в случае с пользовательской Rand?

Код: Выделить всё

Int(6 * Rand()+1)

так правильно?

[Mikle]

Интересно, зачем тут процедура RandInit? 
Похоже что это эквивалент Randomize.

Всё верно.

А какое тогда туда значение посылать r?

Какое угодно, как и в Randomize.

И ещё такой вопрос, как сымитировать выпадения кубика?
Стандартно это так:
Int(6 * Rnd()+1)

а в случае с пользовательской Rand?

Int(6 * Rand()+1)

так правильно?

Правильно.

[Old_Maple]

А вообще, в линейно-конгруэнтном методе

Код: Выделить всё

S(i+1) = A × S(i) + B,

при подборе коэффициентов A и B лучше пользоваться следующим правилом:
квадраты чисел A и B должны быть простыми числами. Например: A^2 = 2, B^2 = 3, тогда A = 1.4142135623731, B = 1.73205080756888. При извлечении квадратного корня из простого числа образуется иррациональное число. Но, так как иррациональное число нельзя засунуть в ограниченное количество разрядов числа двойной точности, то происходит его обрезка. Чтобы исключить снижение разрядности при накоплении суммы S(i) , необходимо данную сумму поделить на коэффициент - С, который тоже является корнем квадратным простого числа. . В моем случае я выбрал C^2=5. А чтобы исключить операцию деления, заменил ее умножением инверсного числа: 1/SQR(5) = 0.447213595499958. Для проверки от переполнения суммы S(i) можно выбрать любое большое число двойной точности >> 1, только чтобы перед плавающей точкой слева было несколько цифр. У меня их до запятой 10: 9876543210.12345(просто последовательный набор всех цифр в обратном порядке до нуля и в прямом - после нуля ).
И тогда алгоритм получится таким:

Код: Выделить всё

Function LCM_Rand() As Single
   'Linear-Congruential Metod - линейно-конгруэнтный метод
   ‘seed = sqr(2) * seed + sqr(3)   
   Seed = 1.4142135623731 * Seed + 1.73205080756888
   If Seed > 9876543210.12345 Then Seed = Seed * 0.447213595499958   'seed = seed * (1 / sqr(5))
   LCM_Rand = Seed - Int(Seed)
End Function

Как видите, почти то же самое, что и у Mikle, только с некоторыми пояснениями.

[neit95]

VB'шную RND на "повторябельность" не проверял, но проверял на вероятность выпадения какого-либо числа (распределением вроде зовётся). Так вот, заваливала края.