О Random и RandomRange

Вопросы программирования на Free Pascal, использования компилятора и утилит.

Модератор: Модераторы

Re: О Random и RandomRange

Сообщение Сквозняк » 06.07.2021 02:29:12

Просто грязная имитация рандома формулой легко ищется в поисковике. Но это на крайний случай, хак чтобы по быстрому что-то залепить.
Код: Выделить всё
1
program primer;

{LCG - Linear congruential generator}
const
  LCG_M = 32767;
  LCG_A = 1103515245;
  LCG_C = 12345;
const
  {состояние}
  LCG_Curr: dword = 1;

  procedure LCG_Init(a: word);
  begin
    LCG_Curr := a;
  end;

  function LCG: word;
  begin
    LCG_Curr := LCG_Curr * LCG_A + LCG_C;
    LCG := hi(LCG_Curr) mod LCG_M;
  end;

var
  k: integer;
begin
  LCG_Init(1); {можно инициализировать секундами текущего времени}
  for k := 1 to 5 do
    writeln(LCG);
end.

Три константы занимаются сексом и заполняют массив своим выхлопом.
Сквозняк
энтузиаст
 
Сообщения: 1109
Зарегистрирован: 29.06.2006 22:08:32

Re: О Random и RandomRange

Сообщение Vadim » 06.07.2021 02:36:48

iskander писал(а):... но я сильно подозреваю, что получится изрядно тормозная штука.

Тут, конечно, без проведения экспериментов вряд ли что можно сказать. Но, совершенно точно известно, что у каждого рандома основа для генерации должна быть своя, независимая друг от друга. Я, к примеру, когда нужно сгенерировать большое кол-во равномерно разбросанных данных (массив) для какой-нибудь вероятностной штукенции, использую свой генератор, наподобие фортрановского, который мне в массив накидывает квазислучайных чисел. У каждого генератора свой аналог RandSeed.
Vadim
долгожитель
 
Сообщения: 4112
Зарегистрирован: 05.10.2006 08:52:59
Откуда: Красноярск

Re: О Random и RandomRange

Сообщение runewalsh » 06.07.2021 03:12:34

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

Вихрь Мерсенна — тоже формула, как и LCG (в твоём коде) или PCG (в моём). То, что у него гораздо больше период, не говорит о том, что он хорош, а совсем даже наоборот. Ознакомься, особенно про decorrelation. Вот так (см. картинки) выглядит неидеальное пересечение некоторыми генераторами состояния из почти одних нулей, а у вихря Мерсенна оно растягивается не на пару десятков итераций, а на СОТНИ ТЫСЯЧ. Как раз потому, что в идеале для получения следующего состояния он должен «перемешать всё внутри себя», что заняло бы N^2 шагов (где N=623) и сделало бы его очень медленным, поэтому он «лениво» перемешивает за N и в результате получает большие проблемы с декорреляцией, среди прочих. Жирные генераторы на это обречены.

iskander писал(а):но я сильно подозреваю, что получится изрядно тормозная штука.

Я проверял threadvar применительно к вихрю Мерсенна. У него много проблем.

Во-первых, компилятор тупит и обращение к КАЖДОЙ threadvar-переменной (а не только, скажем, первой в скоупе) предваряет кодом по работе с threadvar — в этом можно убедиться по ассемблерному листингу. Чтобы это обойти, с ними нужно работать как-то так:
Код: Выделить всё
// Плохой пример — ОЧЕНЬ МЕДЛЕННО
threadvar
   a, b, c, d, e, f: integer;

begin
   // шесть обращений к TLS
   a := b + c;
   d := e + f;
end;

// Лучше
type
   pMyVars = ^MyVars;
   MyVars = record
      a, b, c, d, e, f: integer;
   end;

threadvar
   tlvars: MyVars;

var
   tlp: pMyVars;

begin
   tlp := @tlvars; // одно обращение к TLS
   tlp^.a := tlp^.b + tlp^.c;
   tlp^.d := tlp^.e + tlp^.f;
end;

Этот приём иногда используется и внутри самой RTL. На практике может и не прийтись так всё расписывать, например, если MyVars — объект и мы вызываем его метод, а не работаем с полями непосредственно, self «кэшируется» так же, как здесь вручную кэширован @tlvars.

Так вот, вихрь Мерсенна на первом варианте threadvar замедляется в 22 раза, на втором — «всего лишь» в 4, что всё равно ужасно.

ВО-ВТОРЫХ. threadvar-блок инициализируется для каждого потока НУЛЯМИ. Неприятный момент в том, что у вихря Мерсенна, как и других F₂-генераторов (например, WELL), нулевое состояние не просто «плохое», а НЕДОПУСТИМОЕ — генератор станет ВЕЧНО возвращать нули. Поэтому его придётся инициализировать вручную (ну или проверять инициализированность в каждом вызове), что даже не проще, чем объявить и инициализировать локальный. И наоборот, если генератор сделан как объект, можно получить из него глобальный, объявив, ну, глобальный экземпляр ({global} var rng: Random;), или локальный для потока, объявив как threadvar (threadvar tlrng: Random;).
Аватара пользователя
runewalsh
энтузиаст
 
Сообщения: 578
Зарегистрирован: 27.04.2010 00:15:25

Re: О Random и RandomRange

Сообщение Alex2013 » 06.07.2021 17:41:59

iskander писал(а):своё собственное состояние генератора для каждого потока можно получить запихав его в TLS(threadvar),

Вот, наконец то кто-то, что-то действительно умное сказал ...
iskander писал(а): но я сильно подозреваю, что получится изрядно тормозная штука.

С какой стати ? Последовательность случайных чисел генерируется на основе текущего значения .
(ИМХО) Заставить принудительно посчитать следующее значение зная предыдущее совсем несложно.
Alex2013
долгожитель
 
Сообщения: 2924
Зарегистрирован: 03.04.2013 11:59:44

Re: О Random и RandomRange

Сообщение Сквозняк » 06.07.2021 19:18:51

runewalsh писал(а):В качестве внутреннего алгоритма рекомендую Xoshiro128**/32 или PCG64/32, вот мои реализации:

Как-то не хочется в этот замечательный синтаксис погружаться. Они тестировались на выход за диапазон и предусмотрено ли в них его преодоление, то есть сброс куда-то в начало? Что-то там проверок с большой константой не заметно.
Сквозняк
энтузиаст
 
Сообщения: 1109
Зарегистрирован: 29.06.2006 22:08:32

Re: О Random и RandomRange

Сообщение runewalsh » 07.07.2021 03:42:14

Эти Next'ы возвращают значения из полного диапазона uint32, способ получения из них значений из нужного интервала — вне компетенции алгоритма. Проще всего через mod: например, generator.Next mod 5 возвращает значение от 0 до 4. Для делителей, не являющихся степенями двойки, этот способ смещённый (biased), вот здесь есть разные варианты исправления смещённости. Один из них, пожалуй, самый продвинутый, обычно не делает ни одного div или mod.

Или, если ты про отключение проверок ($rangechecks бла-бла-бла), то так и надо, все внутренние операции переполняются и работают по модулю. Добро пожаловать в удивительный мир компьютерной математики.
Аватара пользователя
runewalsh
энтузиаст
 
Сообщения: 578
Зарегистрирован: 27.04.2010 00:15:25

Re: О Random и RandomRange

Сообщение Сквозняк » 07.07.2021 16:39:22

runewalsh писал(а):Добро пожаловать в удивительный мир компьютерной математики.

Если глубоко вникать в дебри математики, то на логику сил мало останется, а программы больше из логики состоят чем из математики.
Вопрос в том, что случится, после того, когда next выдаст данные из конца массива: заглючит, закольцуется, уйдёт в стабильную петлю, в уменьшающуюся. Вот что нужно знать. Неужели перед рекламой формул, никто не протестировал их на работу не только по середине диапазона, но и по краям?
Сквозняк
энтузиаст
 
Сообщения: 1109
Зарегистрирован: 29.06.2006 22:08:32

Re: О Random и RandomRange

Сообщение runewalsh » 07.07.2021 18:13:56

У последовательности чисел, выдаваемой типичным ГПСЧ, нет «середины», «начала» или «конца», она представляет собой единственное кольцо из 2^64 элементов для PCG64/32 или 2^128 для Xoshiro128**. Задавая seed, ты прыгаешь в некоторую (одну и ту же для одинаковых seed, но в остальном непредсказуемую) точку этого кольца. Какие массивы, о чём речь вообще.
Аватара пользователя
runewalsh
энтузиаст
 
Сообщения: 578
Зарегистрирован: 27.04.2010 00:15:25

Re: О Random и RandomRange

Сообщение Сквозняк » 07.07.2021 20:40:27

runewalsh писал(а):Какие массивы, о чём речь вообще.


Обычные массивы. Вышеприведённые формулы предоставляют услуги чтения из условного массива. Если потратить много памяти и записать данные, а потом прыгать в нужное место массива и последовательно читать по одному его элементу, то результат будет тот же самый что и у твоих функций. Закольцованность условного массива по формуле не видна, потому неясно что будет после достижения конца этого массива - закольцованность или баги. Что не проверено, то представляет опасность.
Сквозняк
энтузиаст
 
Сообщения: 1109
Зарегистрирован: 29.06.2006 22:08:32

Re: О Random и RandomRange

Сообщение runewalsh » 07.07.2021 21:05:37

Ещё раз говорю, у этой последовательности нет начала и конца, ты их сам придумал в момент, когда решил записать её в массив.

По сути, у тебя возникло представление (запись в массив) о предмете (ГПСЧ), которое столкнулось с противоречием (у массива есть конец, что происходит в момент его достижения?). Адекватных людей возникновение такого противоречия заставит засомневаться в первую очередь в состоятельности своего представления, а не самого предмета.

Зацикленность последовательности очевидна из принципа Дирихле, а период вычисляется математически, например, для LCG и основанного на нём PCG известны требования к константам для достижения максимально возможного периода (2^число_бит_состояния). Но у тебя были удивительные оправдания, почему математика неок.
Аватара пользователя
runewalsh
энтузиаст
 
Сообщения: 578
Зарегистрирован: 27.04.2010 00:15:25

Re: О Random и RandomRange

Сообщение Сквозняк » 07.07.2021 21:30:02

runewalsh писал(а):Ещё раз говорю, у этой последовательности нет начала и конца, ты их сам придумал в момент, когда решил записать её в массив.

По сути, у тебя возникло представление (запись в массив) о предмете (ГПСЧ), которое столкнулось с противоречием (у массива есть конец, что происходит в момент его достижения?). Адекватных людей возникновение такого противоречия заставит засомневаться в первую очередь в состоятельности своего представления, а не самого предмета.

Как писал Блёз Паскаль, в честь которого и был назван язык программирования паскаль, мало кто шарит и в математике и в логике - обычно в чём-то одном. Людские ресурсы не резиновые. Практика показывает что условные массивы таки есть и их можно записать на носители, если хватит их размера, а потом тупо оттуда доставать. До математиков это не доходит. А значит можно и условное начало отметить, например, значение после инициализации нулём или единицей.
Код: Выделить всё
VAR
SUKA_R1: Xoshiro128ss_32;
Q2:LONGINT;
SUKA_R2: Pcg64_32;

BEGIN
SUKA_R1.Setup(1000);
FOR Q2:=1 TO 20{00} DO WRITE(SUKA_R1.NEXT MOD 255,' ');
WRITELN(#13#10#13#10#13#10#13#10);
SUKA_R2.Setup(1000);
FOR Q2:=1 TO 20{00} DO WRITE(SUKA_R2.NEXT MOD 255,' ');
WRITELN;
END.

А на выхлопе три раза подряд вот это:
Код: Выделить всё
./suka_random
14 3 98 244 167 119 70 154 238 40 166 80 226 115 125 235 109 223 245 81




56 90 125 67 212 182 121 54 11 71 30 71 27 58 112 120 109 39 43 83

Зацикленность последовательности очевидна из принципа Дирихле,

:mrgreen: :mrgreen: :mrgreen: :mrgreen: :mrgreen: Что в нём очевидного? В компьютере всё проверять надо. Подставлять значения и запускать. Если результат удовлетворительный, дальше можно пользоваться.
runewalsh писал(а): например, для LCG и основанного на нём PCG известны требования к константам для достижения максимально возможного периода (2^число_бит_состояния). Но у тебя были удивительные оправдания, почему математика неок.

Ну и как, протестировали Pcg64_32; с такими числами, куда потом в условном массиве сдвинется условный индекс или нет? Типа помедитировали на Дирихта и дело сделано.

Добавлено спустя 2 часа 38 минут 13 секунд:
Да, если бы математики в штатном рандоме не устроили в потоках жуткий дефицит мелких значений выхлопа. Эта тема не состоялась бы.
Сквозняк
энтузиаст
 
Сообщения: 1109
Зарегистрирован: 29.06.2006 22:08:32

Re: О Random и RandomRange

Сообщение Alex2013 » 08.07.2021 11:52:29

"Боюсь спросить " а про нормализацию распределения случайных чисел( и тому подобные приемы ) что совсем никто ничего не слышал ? :roll:
"Навскидку..."
https://habr.com/ru/post/208684/
https://korobchinskiy.com/generaciya-sluchainyh-chisel/
https://planetcalc.ru/5840/
http://kafais07.narod.ru/page/randomaze.htm
...
Alex2013
долгожитель
 
Сообщения: 2924
Зарегистрирован: 03.04.2013 11:59:44

Re: О Random и RandomRange

Сообщение Vadim » 08.07.2021 16:34:12

Alex2013
Слышали, естественно, все. Но товарищ вопрошающий непременно хочет, чтобы само собой, без хогвардских заклинаний... ;-)
Vadim
долгожитель
 
Сообщения: 4112
Зарегистрирован: 05.10.2006 08:52:59
Откуда: Красноярск

Re: О Random и RandomRange

Сообщение Сквозняк » 08.07.2021 17:36:20

Vadim писал(а):Но товарищ вопрошающий непременно хочет, чтобы само собой, без хогвардских заклинаний... ;-)

Заклинания нужно тестировать чтобы определить их границы применимости, чтобы знать нужно ли молотилку чисел перезапускать или сохранять её данные для продолжения, и вообще, как применять. А математики вместо ответов на конкретные вопросы любят упомянуть несколько заклинаний, которые непонятно как прилепляются к коду, и делать страшное лицо - верьте что подсчитано качественнее чем у астрологов. В компутерах математика особая, её протестировать надо, вдруг в нём такое накодено и при применении рванёт:
Код: Выделить всё
function umnozitelj(A,B: longint): int64;
begin
umnozitelj:=A*B;
if A=2 then if B=2 then inc(umnozitelj);
end;

С делением на ноль постоянно подобное писать приходится, вдруг и для умножения такое накодили а потом забыли :mrgreen:
Сквозняк
энтузиаст
 
Сообщения: 1109
Зарегистрирован: 29.06.2006 22:08:32

Re: О Random и RandomRange

Сообщение Vadim » 08.07.2021 18:36:24

Сквозняк писал(а):Заклинания нужно тестировать чтобы определить их границы применимости...

Ну да, ну да... А тестировать неохота... Охота, чтобы пришёл кто-то мудрый и сказал: делать так и перетак... И при этом хорошо бы ещё поднял указующий перст к небосводу... И неважно, что с тестированием задача решается в 10 раз быстрее - ждём сакральной мудрости... ;-) :-)
Vadim
долгожитель
 
Сообщения: 4112
Зарегистрирован: 05.10.2006 08:52:59
Откуда: Красноярск

Пред.След.

Вернуться в Free Pascal Compiler

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 21

Рейтинг@Mail.ru