Как случайный зритель отмечу - capzar признал правоту владимира в 174 посте, а владимир опять срывается до неуважительного отношения. Пример "и без включения мозга", как в 176 посте, хорошо это показывает. Знания - знания, но так самоутверждаться...
Знаете лучше - спокойно объясните без нервных срывов. Берите пример с Petera, великий человек. Ни разу не видел подобного отношения даже к самому ''трудному' собеседнику.
О, мнения зрителей, безусловно, интересны. Полагаю, имелось ввиду 173.Сообщение от IIeroniux
Но не считаете ли вы, что порядочный человек должен хотя бы извиниться?
Действительно ли по-вашему достаточно фразы capzap'а "я убедился что xorshift лучше, одного не пойму так трудно было сразу все предоставить, ..., если по другому не вытянуть"?
В #21 было же все предоставлено. Чего тогда человек "вытягивал" на протяжении 21...173?
Я даже пару раз суммировал #74, #113.
ну в общем то пару замеров на ночь глядя не показатель, сегодня при 5000 генераций всё нормально, при 10000 с чего то вдруг переменная sum начала принимать значения в 3 раза больше максимально возможных единиц, хотя среднее показывает как обычно в пределах 0.5, от метода не зависит
ЗЫ выложил еще один генератор, как должен был бы выглядеть генератор от И.Петрова
Последний раз редактировалось capzap; 20.07.2016 в 09:10.
Bad programmers worry about the code. Good programmers worry about data structures and their relationships
среди успешных людей я не встречала нытиков
Барбара Коркоран
capzap, я позволю себе НЕ бегать за ПЛК, а найду ошибку в вашем коде. Надеюсь, после этого вы ещё раз подумаете над тем "проходит ли xorshift128 тест frequency".
Вот вы показывали пример, где, якобы, "значение sum выходит за все мыслимые границы":
Ошибка в первом условии IF count < idx+1 THEN.
Должно быть <=. Т.е. IF count <= idx+1 THEN
Сейчас получается, что вы значение stuff[idx+1] не записываете, а потом пытаетесь из него читать.
На вашей же картинке ясно видно, что stuff[count] == 16177 и count==idx+1. Ну не может такое число быть результатом операции BOOL_TO_INT.
И, да, переменная sum это сумма -1 или +1. Сумма 10001 таких чисел никак не может выйти за диапазон -10001...+10001. У вас получилось 32144, что должно было вас насторожить, но вы почему-то сделали вывод "генератор плохой", а должны были сделать вывод "в коде ошибка".
Ещё раз картинка, про которую я говорю: owen.png
поясните мне не математику ,что плохого в случайной последовательности чисел ,в которой исключены "склейки" -повторение подряд одинаковых чисел .Я понимаю что такое может быть по теории вероятности ,если бочонки вытащенные из мешка опять бросаются в мешок ,но мне не нужна такая последовательность .Мне нужно ,что бы было как в игре старинной -лото .Вытащил бочонок из кубышки и его уже нет в списке .После последнего бочонка снова тусуем мешок и продолжаем вытаскивать бочонки (но без повторения значений) ...Вот что плохого в таком алгоритме генерации случайного числа? .Количество бочонков в мешке- это диапазон случайных чисел .
Для меня "склейки" на фоне белого шума" это щелчки .
Последний раз редактировалось rovki; 20.07.2016 в 09:28.
электронщик до мозга костей и не только
0) Для каких-то задач "генератор без повторений" может и потребоваться. Но слепо использовать его для всех задач -- нехорошо.
Если говорить чем "в целом" плох генератор, который выдаёт циклами без повторений, то
1) Плохо то, что он предсказуем. Например, если генерируем числа от 0 до 4, и 0, 1, 2, 3 уже выпали, то с вероятностью 100% выпадет число 4.
2) Плохо то, что нет эффективной реализации для произвольного диапазона. Нет от слова "совсем". Хорошую реализацию можно сделать через массив. Т.е. заполнить его числами от 0 до N, перемешать, и выдавать по одному. На ST это тривиально, а в ОЛ уже проблематично. Но, стоит понимать, что большие массивы держать в памяти и перемешивать всё равно время займёт.
3) Для частных случаев (некоторых N) можно сделать алгоритм не требующий массива, но он при этом будет выдавать лишь часть из возможных перестановок.
Последний раз редактировалось Владимир Ситников; 20.07.2016 в 10:33.
0) Не хорошо не приводить расчеты и аргументы ,а только фразы
1)Для меня равновероятно ,имхо -это когда каждое число может выпасть с равной вероятностью .для 1из 10 -10% ,а 1 из 1-100% ,естественно .Тоесть сначала вероятность у всех 10% ,потом 11.1 ,12.5 ,14.3, 16.7 ,20 ,25,33.3,50,100. по сравнению с начальной кучей .Тоесть вероятность растет у оставшихся по сравнению с общей кучей (10шт) ,но между собой они имеют равную вероятность быть выташенными ,что 3 из 3 ,что 5 из 5 каждый имеет равную вероятность .Меня не интересует вероятность оставшихся по сравнению с общей кучей ,меня интересует выроятность вытащенных значений (генерации) между собой .Да, цикл (куча) генерится вновь ,поэтому не 1из 1 остается ,а постоянно 1 из 10
2)использование массивов не представляется возможным при разности скоростей приема\передачи в 10раз ,ни какого стека не хватит ,он переполнится .
Последний раз редактировалось rovki; 20.07.2016 в 11:33.
rovki, попробуйте понять, что есть 2 различные задачи: "простой ГСЧ" и "ГСЧ без повторений".
То, что описываете вы (игра лото с бочонками, 5 из 36 и т.п.) это "ГСЧ без повторений".
Но не надо лезть с этой своей задачей "ГСЧ без повторений" в тему, где обсуждается простой ГСЧ. Это две разные задачи, со своими границами применений.
Можете ещё раз объяснить почему "использование массивов не представляется возможным"? Вот не понимаю ваших опасений про "стек переполнится" и "разности скоростей".
В чём принципиальная проблема выделить 8-128 байт ОЗУ на то, чтобы хранить массив бит?
От таких объёмов в самом ПР ничего не переполнится. Возможно, получится даже сами числа хранить, т.е. массив чисел (word или dword)
А ничего что я уже написал сей макрос?
Который генерирует число от 0 до n без повторений, где n произвольное, меньше 1024.
А называется макрос rnd1024.
PS если есть желание, сам генератор можно легко поменять на ваш, а обработчик массива оставить мой.
Последний раз редактировалось AI!; 20.07.2016 в 11:49.
начинающий профессионал
Поясню, что я имею ввиду: по сути, задача "выборки n значений от 0 до n-1 без повторений" эквивалентна задаче "генерации случайной перестановки чисел от 0 до n-1" (по-английски это random shuffle)
1) Задача random shuffle обычно решается через массив: Тасование Фишера–Йетса
Если бы было можно просто "брать и генерировать очередное значение", то такой алгоритм наверняка бы упомянули в wikipedia. Но, нет, там про тасовку значений пишут, что всё-таки нужен массив, и при реализации Фишера–Йетса нужно быть внимательным, т.к. легко ошибиться и тасовка станет очень плохой.
Кстати, в OSCAT функция _ARRAY_SHUFFLE неправильная (там в 2 раза меньше перестановок чем надо, там плохой генератор и т.п.): https://github.com/simsum/oscat/blob...LE.EXP#L27-L34
Следующий момент -- для генерации перестановки большого количества элементов нужен ГСЧ очень высокого качества.
Например, из 1024 элементов есть 1024! перестановок. Для кодирования такого количества нужно log(1024!, 2) бит информации, т.е. примерно 8769 бит.
Это почти в 70 раз больше, чем внутреннее состояние xorshift128. Т.е. нужен либо ГСЧ с большим состоянием, либо нужно эффективно подмешивать энтропию "по ходу генерации". Да, тактование (выборка результата ГСЧ в случайный момент) является одним из таких действий, но тут большой вопрос сколько бит энтропии даёт подобное действо.
Получается, нужно крайне аккуратно следить за ГСЧ, иначе большая часть "возможных перестановок" вообще никогда не будет сгенерирована.
2) Есть ещё второй вариант -- pseudorandom permutation. Более известное как "симметричный шифр".
Например если есть алгоритм шифрования, шифрующий значения 0..63 с помощью ключа K, то "псевдослучайную перестановку" можно получить, если зашифровать значения 0, 1, 2 и т.п. последовательно. Т.е. Encrypt(0, K), Encrypt(1, K), и так далее. Разумеется, после каждого цикла нужно менять ключ шифрования и/или алгоритм шифрования.
Но тут 2 вопроса: во первых, ключ шифрования должен быть немалой длины (ну, чтобы хотя бы в теории закодировать все возможные n! перестановок), а во-вторых, на ум не приходят алгоритмы шифрования, у которых входной-выходной диапазон можно менять как параметр.
Ну, можно найти семейство алгоритмов, которые работают в числах 0...2n-1. В частности, 0..63, но если понадобится генератор "от 0 до 62 без повторений", то нужно будет ещё что-то придумывать.
Например, сработает такой алгоритм (но внутренний цикл while(nextValue>n) неудобно реализовывать на ОЛ):
Код:int n=49; // хотим получить перестановки от 0 до n int k=42; // ключ шифрования for(int i=0; i < n; i++) { int nextValue = Encrypt(i, k); // Считаем, что Encrypt выдаёт значения от 0 до 63 while(nextValue > n) { // Если оказалось 50..63, то значение не подходит -- шифруем его пока не попадёт в диапазон 0..49 nextValue = Enrcypt(nextValue, k); // да, повторно шифруем значение, если оно выходит за диапазон } System.out.println("next value = " + nextValue); }
Для справки, ln(64!)/ln(2) == 296. Т.е. для описания всех возможных 64! перестановок нужно почти 300 бит энтропии.
3) Идея с "давайте просто запоминать выпавшие числа, и если выпадет повторно, то бросать кость заново" понятна, но в ОЛ это убого, и приходится идти на уступки вида "если значение уже было, то возьмём просто следующее свободное". Это самое "следующее свободное" нарушает "случайность" перестановки -- т.е. генератор генерирует biased (как оно по-русски? смещённые? неравномерно распределённые?) последовательности.
Последний раз редактировалось Владимир Ситников; 20.07.2016 в 12:26.
Ваши права
