| 0
- 12.12.2013 - 18:43
|
Моя проблема. Модернизируя генератор псевдлслучайных чисел, придумал для тестирования геоиетрическую интерпретацию. По одному его выходному значению формируется координата Х, по другому значению координата У. Точка (Х,У) меняет цвет свой текущий цвет на следующий цвет из массива цветов. В итоге на экране квадрат из цветных точек. Если в квадрате хаотичный набор точек, это будет говорить о приемлимом качестве генератора. Если в квадрате просматривается какая либо закономерность, это будет говорить о плохом качестве генератора. И тут я столкнулся с проблемой. Чтобы не засорять описание ненужными деталями, сведу, без ограаничения общности, к 2-м простым ситуациям. Ситуация 1-я. Две колоды карт перетасовываются (каждая по отдельности) случайным образом. Далее из каждой колоды открывается по одной карте, они образуют первую пару. Аналогично формируются вторая и следующие пары. Когда карты в колодах заканиваются, опять повтояряется тоже самое. И так многократно. Ситуация 2-я. Две колоды карт смешиваются в одну, удвоенную колоду. Эта колода также перетасовываются случайным образом. Затем из колоды по одной окрывается две карты, образующие первую пару. Аналогично формируются последующие пары. Когда колода заканчиваеися, всё опять многократно повторяется Вопрос. Одинакова ли для этих 2-х случаев вероятность выпадения в паре одинаковых (по масти и значению) карт? Моя же геометрическая интерпретация показала, что в первом случае вероятность меньше. Мне это не совсем ясно.     | |
| 41
- 13.02.2014 - 01:49
|
[quote=Boltas;34126017]а как может замкнутая, в каких-то определенных пределах, система вдруг стать идеальным генератором случайных чисел?[/quote] Идеальное в природе отсутствует. Мы всегда имеем нечто упрощенное. Но это не страшно. Никто ведь не страдает от того, что 1/3 не равен 0.333333333...3 | |
| 42
- 13.02.2014 - 01:51
| По поводу того, что есть идеальный генератор очень хороши размышления Д. Кнута в упомянутой книге. | |
| 43
- 13.02.2014 - 06:41
|
41, еще как страдаем... от необходимости выбора точности измерения) а сама необходимость выбор - и есть мучение автор, если взять бесконечное количество колод карт, с бесконечным количеством мастей и номиналов - вполне возможно получится нормальное распределение случайного выбора при этом и цикл будет только один, но бесконечный... значит по идее повторений не должно быть априори имхо | |
| 44
- 15.02.2014 - 04:46
|
[quote=Boltas]если взять бесконечное количество колод карт, [/quote] А где ж их взять-то, кроме как с генератором случайных чисел в бесконечном цикле? [quote=Boltas]с бесконечным количеством мастей[/quote] А это как? Я даже не могу представить, что под этим подразумевается | |
| 45
- 15.02.2014 - 08:41
|
44, под всем этим подразумевается бесконечный трехмерный массив, данные в котором остается лишь перемешать (перетасовать) с помощью гсч... точнее сказать попытаться перемешать, ибо в реальности весь этот массив перемешать невозможно по определению) но, отсутствие пределов - нет отскоков, значит не будет и возможных повторений, их вероятность нулевая а если нужно практическое применение, то достаточно прописать закономерностями тождественность чисел определенным игральным картам, мастям и колодам например туз пик в первой колоде - 1,1,1, а та же карта в сотой колоде 101, 101, 101 как-то так | |
| 46
- 16.02.2014 - 08:51
|
45 Все неверно. Абсолютно все. Зачем говорить о бесконечном массиве, если все равно нам доступен только его конечный кусок? Это эквивалентно конечному массиву. А перетасовка массива с помощью ГСЧ ничем не отличается от самого ГСЧ, кроме лишней работы. Принцип работы программных ГСЧ (если не залезать внутрь) – циклически прокручивать все целые числа в некотором диапазоне (вот он, «перетасованный массив»), обычно (а м.б. и всегда) от 0 до 2 в какой-то степени (в большой!) минус 1. Каждое число за цикл должно встретиться 1 и только 1 раз, дальше цикл повторяется. Цикл большой, поэтому, чтобы заметить повторы, пришлось бы оОочень долго крутить. Плюс требование на последовательность в цикле – чтобы она была максимально похожа (в некотором смысле) на математическую абстракцию «равномерное распределение» + «независимость случайных величин». Возможно, что уавтора все это и так, но цикл слишком мал: 0–255. Отсюда и «черная диагональ» и заметная повторяемость. | |
| 47
- 16.02.2014 - 09:21
|
46-Дюша >цикл большой, цикл слишком мал - самому не смешно от таких определений) вы сами себе противоречите, говоря о том, что [quote=Дюша;34166356]Возможно, что уавтора все это и так, но цикл слишком мал: 0–255. Отсюда и «черная диагональ» и заметная повторяемость.[/quote] vs [quote=Дюша;34166356]Все неверно. Абсолютно все.[/quote] дело в том, что совсем не важно каким именно алгоритмом будем выстраивать случайную последовательность чисел, а важно - откуда будем брать данные для такого алгоритма вы говорите [quote=Дюша;34166356]Зачем говорить о бесконечном массиве, если все равно нам доступен только его конечный кусок? Это эквивалентно конечному массиву. [/quote] но, это не так - не эквивалентно, ибо свойства ведра морской воды отдельно стоящего на вашей кухне не тождественно свойствам десяти литров той же воды, но в мировом океане - это нужно четко понимать если обойтись без аллегорий, то при бесконечном массиве нет диапазона как такового, во время исполнения алгоритма могут участвовать любые числа от минус бесконечности до плюс бесконечности, но есть конешно ограничение по количеству выбираемых элементов в единицу времени, которое обусловлено лишь мощностью вычислителя поэтому ваше - нужно чуть-чуть раздвинуть границы 0-255, например кстати до какого размера нужно их раздвинуть?))) когда "мало" перейдет в "достаточно"?)) | |
| 48
- 16.02.2014 - 14:38
|
Boltas > Можно, я попытаюсь кое-что угадать? Вы по образованию математик. О том, что такое программирование, имеете лишь весьма смутное представление. Угадал? (Для жителей планеты Земля поясню, в чем именно Boltas нашел противоречие. Я сам не сразу догадался. В том, что типа конечного числа (256) маловато, а бесконечность – неправильно.) Встречаются такие математики, которые при виде записи π ≈ 3.14 выдавливают из себя злорадный смех. Мол, такая запись ничем не лучше записи π ≈ 1000: погрешность не указана. Видимо, если таким людям на вопрос, как проити, скажут «примерно через 200 метров сверните налево», они будут искать поворот от минус до плюс бесконечности – погрешность не указали. Надеюсь, что Вы не из таких ;) [quote=Boltas] ибо свойства ведра морской воды отдельно стоящего на вашей кухне не тождественно свойствам десяти литров той же воды, но в мировом океане - это нужно четко понимать [/quote] Нужно четко понимать, что, когда речь идет не о математических абстракциях, а о реальных вещах (комп, программа), «мирового океана» нет, а есть только «ведро». Оно м.б. поменьше или побольше – определяется размером доступной памяти. [quote=Boltas] могут участвовать любые числа от минус бесконечности до плюс бесконечности [/quote] Не могут – по вышеописанной причине. Итого, мы можем располагать только конечным подмножеством целых чисел. [quote=Boltas] совсем не важно каким именно алгоритмом будем выстраивать случайную последовательность чисел, а важно - откуда будем брать данные [/quote] Исходя из вышесказанного, важен именно алгоритм. [quote=Boltas] когда "мало" перейдет в "достаточно"? [/quote] По-моему, это очевидно. Когда период ГСЧ намного больше, чем длина последовательностей, нужных пользователю. Знаю, зацепитесь за «намного больше». Определяется конкретной задачей. Например, если через раз карты будут раскладываться так же, любой заметит. Надо так, чтобы по крайней мере подавляющее большинство не заметило повторяемости. Что такое «подавляющее большинство» обсуждать будем? :) | |
| 49
- 17.02.2014 - 01:19
|
[quote=Дюша;34169636]Угадал?[/quote] нет, не угадал по образованию я программист, но и с математикой немного знаком [quote=Дюша;34169636]а есть только «ведро». Оно м.б. поменьше или побольше – определяется размером доступной памяти. [/quote] снова не верно память у вычислителя может быть сколь угодно большой - это и есть "мировой океан" а вот мощность процесса обработки данных (количество обращений к памяти в ед.времени) - есть величина конечная, я об этом уже упоминал выше [quote=Дюша;34169636]Не могут – по вышеописанной причине.[/quote] могут вопрос лишь в методе снятия полученных промежуточных результатов... и конечно невозможно при помощи стандартного программинга, ну тем, что вы называете программированием [quote=Дюша;34169636]Исходя из вышесказанного, важен именно алгоритм.[/quote] отчасти да, но алгоритмов как раз великое множество поэтому в принципе подобрать его не проблема или, например, собрать свой из нескольких [quote=Дюша;34169636]Определяется конкретной задачей.[/quote] а причем здесь задача? тема сабжа - получение полуфабриката (последовательность равномерно распределенных случайных чисел), а для чего именно вы потом используете этот фарш... можно сделать колбасу, можно котлеты - это уже другой вопрос [quote=Дюша;34169636]Что такое «подавляющее большинство» обсуждать будем? :)[/quote] а надо?) дело в том, что подавляющее большинство думает также, как и вы | |
| 50
- 17.02.2014 - 11:08
|
[quote=Boltas;34175763]тема сабжа - получение полуфабриката [/quote] Постепенно она перешла в словесный онанизм. Пора прекратить треп ни о чем. | |
| 51
- 17.02.2014 - 23:18
|
50, а шо так? как только разговор вышел за рамки вашего понимания, так сразу - трёп) | |
| 52
- 18.02.2014 - 05:38
|
[quote=Boltas] память у вычислителя может быть сколь угодно большой [/quote] Вот можно с этого места поподробнее? А то как-то не верится. [quote=Boltas] и конечно невозможно при помощи стандартного программинга [/quote] Раскорйте уж все карты [quote=Boltas] а причем здесь задача? … а надо?) [/quote] Это я писАл а предположении, что УГАДАЛ | |
| 53
- 18.02.2014 - 07:40
|
[quote=Дюша;34190225]Вот можно с этого места поподробнее? А то как-то не верится. [/quote] например, интернет как база данных, а пауки гугла, яндекса и прочих поисковых систем - вычислители такая база данных не имеет ограничений не только по размеру, но и по структуре представления данных [quote=Дюша;34190225]Раскорйте уж все карты[/quote] ничего секретного в этом нет если говорить непосредственно о задаче по сабжу, то возможен такой вариант например - плавающие диапазоны... по линии, в плоскости или в пространстве многомерного массива размеры диапазонов (выборки) ограничены лишь мощностью вычислителя, а пространство их "плавания" не ограничено, то бишь бесконечно конкретный размер и точка отсчета в данный конкретный момент определяется результатами предыдущих вычислений - вот здесь уже зависит от выбранного алгоритма зачем так сложно? на самом деле здесь ничего сложно нет, но этим мы добиваемся главного - нет точки останова и повторного запуска главного вычисления, он зациклен и никогда не останавливается, значит процесс не будет проходить по одним и тем данным тысячи раз, выдавая на гора похожие результаты итерации присутствуют только при вычислении промежуточных результатов в плавающих диапазонах | |
| 54
- 19.02.2014 - 17:59
|
[quote=Boltas] например, интернет как база данных … [/quote] У меня такое предположение было, но я его отмёл – бесконечности смутили. [quote=Boltas] такая база данных не имеет ограничений не только по размеру [/quote] Как это? На планете конечное число компов, в каждом конечный объем памяти. Кроме того, кто же позволит этот весь огромный объем использовать только для того, чтобы Вася Пупкин (ни на кого не намекаю) сделал себе ГСЧ? [quote=Boltas] зачем так сложно?[/quote] Вот это точно! Из пушки по воробьям, когда есть простые, автомомные, быстрые и полностью удовлетворительные методы. | |
| 55
- 19.02.2014 - 19:59
|
54, абзац1, зря вас пугают бесконечные числа... достаточно ввести предел по точности и бесконечность вдруг обретает вполне осязаемое числовое значение, но точность ведь тоже может быть не константой, а переменной, и в таком качестве участвовать в алгоритме абз.2, причем здесь пупкин с своим гсч? интернет я привел всего лишь в качестве примера громадной базы данных, а не как основу для разработки генератора... хотя в этом что-то есть, учитывая неоднородность её данных - вполне так норм основа, только трудоемкая в обработке а насчет конечного количества байтов в интернете в сию секунду времени... так и наша бесконечная вселенная имеет конечную цифру по возрасту и по размерам тоже)) просто вопрос в масштабах абз.3, если реально, то эти простые и быстрые алгоритмы уже не могут удовлетворить все потребности современного программинга... например, в криптографии - мощность вычислителей (прежде всего железа) растет в геометрической, а алгоритмы шифрования... ну как бы до сих пор дешифруются простым перебором хешей а почему так? да, потому что все (включая и дешифраторов) знают - заложено конечное число вариаций п.с. но, в области криптографии я не силен чес говоря, могу быть и не в курсе новинок, м.б. уже что-то там глобально изменилось | |
| 56
- 20.02.2014 - 19:18
|
[quote=Boltas] достаточно ввести предел по точности и бесконечность вдруг обретает вполне осязаемое числовое значение … просто вопрос в масштабах [/quote] Вас, помнится, веселили мои формулировки про масштабы (47). Вы то же самое и говорите, что и я, только цифири побольше Вот сами на свой вопрос [quote=Boltas] 47 – когда "мало" перейдет в "достаточно"? [/quote] и ответили. Только всем достаточно вовсе не астрономических чисел. Вы утверждали, что важен не алгоритм, но в 53 описали наброски именно алгоритма (надо сказать, ничего не понял). | |
| 57
- 20.02.2014 - 20:24
|
56-Дюша >не нужно выдергивать слова из контекста, дословно я сказал так [quote=Boltas;34166532]дело в том, что совсем не важно каким именно алгоритмом будем выстраивать случайную последовательность чисел, а важно - откуда будем брать данные для такого алгоритма[/quote] [quote=Дюша;34236041]надо сказать, ничего не понял[/quote] это я понял... так спросите, вместо поиска противоречий в моих постах | |
| 58
- 21.02.2014 - 16:42
|
[quote=Boltas;34166532]дело в том, что совсем не важно каким именно алгоритмом будем выстраивать случайную последовательность чисел,[/quote] Но очень важно, лявляется ли генератор "правильным", такие ли у него результаты тестов, как получаются из теории при совершенно случайном источнике. | |
| 59
- 21.02.2014 - 17:20
|
58, да, конечно это важно... выше по сабжу здесь приводились методы проверки, например мне очень понравился вариант автора топика с цветной визуализацией и что? | |
| 60
- 23.02.2014 - 08:50
|
Цветная визуализация, конечно, не годится, я об этом писал. По поводу Вашего метода. Давайте разложим по полочкам. Итак, с бесконечностями мы вопрос утрясли. Никаких бесконечностей нет, а есть массив конечной (пусть и большой) длины, в котором лежат числа из некоторого конечного диапазона [a, b] (ведь так?). Вопросы будут маленькими порциями. Каждое число представлено в массиве единожды или нет? Если нет, то что можно сказать про количества представлений каждого числа в массиве? Как они в массиве расположены? | |
| 61
- 25.02.2014 - 09:14
|
[quote=Boltas;34189320]как только разговор вышел за рамки вашего понимания, так сразу - трёп[/quote] Абсурд вне понимания. Пока что видно, что обсуждатели не понимают, что такое генератор псевдослучайных чисел, как его проверять, какова "мощность проверки". | |
| 62
- 25.02.2014 - 19:15
|
[quote= x_05772] обсуждатели не понимают [/quote] А почему, собственно, во множественном числе? | |
| 63
- 25.02.2014 - 22:55
|
[quote=Дюша;34304450]А почему, собственно, во множественном числе?[/quote] Надир Дюша x_05772 Boltas | |
| 64
- 26.02.2014 - 01:56
|
Перейдем от негатива к позитиву. генератор (псевдо)случайных чисел - нечто программное, выполняющее 1 задание начального значения примерно так randseed:=12345; 2 получение очередного значения p:=nextrandom; обычно выдается равномерно распрелеленная величина в диапазоне 0...0.9999, но она получается нормировкой из целого значения 0..2^32 У хорошего генератора любая подпоследовательность не отличима от настоящей случайной последовательности. Так что управлять им не нужно и бессмысленно. Разных генераторов было придумано много. Однако выжил линейный конгруентный. Потому что он прост, и для него можно много чего доказать. Прочие сильно сократилсь в числе в конце 1960х. После кучи скандалов, связанных с тем, что их использование при моделировании монтекарлой давало большие и странные ошибки. К сожалению, есть ещё много темных пользователей, считающих, что они сами с усами и могут такую ерундовинку и сами написать. Умные математики, любящие точность, напридумали много тестов, которые проверяют качество генераторов. В последней версии DIEHARD 31 штука. К сожалению, некто Надир обо всем этом ничего не знает, и как Кулибин создал свой, неповторимый. Борьба с ним, повидимому, безнадежна. [quote=Дюша;34267361]Каждое число представлено в массиве единожды или нет?[/quote] И ежу ясно, что если количество чисел в массиве > его длины, то будут повторы.[quote=Дюша;34267361]Если нет, то что можно сказать про количества представлений каждого числа в массиве?[/quote] А это без тщательного анализа алгоритма не выяснить. Хотя вероятно, когда длина массива велика, а диапазон значений мал, примерно каждое значение будет L/256. Но это очень слабый тест. Так что не изобретайте велосипеды. | |
| 65
- 26.02.2014 - 18:50
|
[quote= x_05772] Надир Дюша x_05772 Boltas [/quote] Ну хоть ладно, что и самого себя включтли в список непонимающих :) [quote=x_05772] некто Надир… Борьба с ним, повидимому, безнадежна. [/quote] Напомню, что некто Надир не бороться с ним просил, а помочь, что следует из названия темы. [quote=x_05772] Цитата: [quote=Дюша]Каждое число представлено в массиве единожды или нет? Если нет, то что можно сказать про количества представлений каждого числа в массиве? [/quote] И ежу ясно, [/quote] И ежу ясно, что эти вопросы адресованы Boltas, и отвечать за него было, мягко говоря, бессмыссленно. | |
| 66
- 26.02.2014 - 18:53
|
ого, сколько написали... 64-x_05772, поймите меня правильно: 1. я никому не навязывю свой генератор, я его сделал чисто для себя. 2. данная тема, открытая мною, напрямую с проболемами генератора никак связана не была, я только упомянул мимоходом, откуда возникли мои вопросы 3. под управлением генератором я имел ввиду возмлжность задавать генератору следующее режимы: 3.1. сбрасываться в начальное состояние 3.2. запоминать любое текущее состояние 2.3. начинать работу с запомненного состояния | |
| 67
- 26.02.2014 - 19:46
|
[quote=Дюша;34320335]Напомню, что некто Надир не бороться с ним просил, а помочь, что следует из названия темы.[/quote] Его надо оттащить от самопального генератора. Без борьбы не получится. [quote=Надир;34320373]1. я никому не навязывю свой генератор, я его сделал чисто для себя.[/quote] Независимо от для кого и для чего, генратор должен быть правильным.[quote=Надир;34320373] ого, сколько написали... 64-x_05772, поймите меня правильно: 1. я никому не навязывю свой генератор, я его сделал чисто для себя. 2. данная тема, открытая мною, напрямую с проболемами генератора никак связана не была, я только упомянул мимоходом, откуда возникли мои вопросы 3. под управлением генератором я имел ввиду возмлжность задавать генератору следующее режимы: 3.1. сбрасываться в начальное состояние 3.2. запоминать любое текущее состояние 2.3. начинать работу с запомненного состояния [/quote] Главный вопрос - зачем придумывать очередной паровоз. Причем с кривыми колесами. [quote=Надир;33300120]Вопрос. Одинакова ли для этих 2-х случаев вероятность выпадения в паре одинаковых (по масти и значению) карт?[/quote] Есть как минимум 2 пути 1 сугубо экспериментальный. Наделать длинную последовательность, обработать и проверить на соответствие с гипотезой о равномерно распределенной некоррелированной. Всего то делов 1 нагенерировать 12E6 значений взять DIEHARD и пусть он сам всё проверит. 2 Взять тщательно скрываемый алгоритм генерации и пыхтя и потея получить формул для всяческих статистических величин. Ни того, ни kheujuj нет. Надир залает загадки как сказочный царь: пойли туда, не знаю куда. Найди то, не знаю что. Так что нечего тут больше говорить. | |
| 68
- 26.02.2014 - 20:18
|
67-x_05772, в этой теме никто не спрашивал меня, по какому именно алгоритму работает мой генератор, а я не навязывался. Никакой тайны тут нету. Вот ссылка на одну из тем, где в 9-м посту я приводил алгоритм. [url]http://forums.kuban.ru/f1024/generator-4811023.html#post32389578[/url] | |
| 69
- 26.02.2014 - 20:40
|
Опишу алгоритм на словах. Есть массив случайных 2-х битовых чисел (каждое в диапазоне от 0 до 3), длиною в 251 число. Есть 12 независимых индексов. По этим индексам из массива вытаскивается 12-ть 2-х битовых чисел. Из этих 12-ти чисел путём наложения логической операцией "исключающен или" формируется 8-ми битовое число, которое и является выходным. Каждый из этих индексов наращтвается на единицу. Для каждого индекса существует свой предел, при достижении которого индекс сбрасывается в нуль. Пределы таковы 191,193,197,199,211,223,227,229,233,239,241,251 это всё простые числа. Таким образом, генератор позволяет формировать неповторяющуюся последовательность в 191*193*197*199*211*223*227*229*233*239*241*251 случайных чисел, что составляет около 10**38. | |
| 70
- 26.02.2014 - 20:48
| Таким образом, данный генератор можно считать 'табличным' :^) | |
| 71
- 27.02.2014 - 19:40
|
[quote=Надир ] Есть массив случайных 2-х битовых чисел [/quote] Неправильное утверждение. Массив задан, это константа. Возможно, подразумевалось, что он заполнен с помощью какого-то источника случайности (та же монетка). Есть простой и действенный способ: N[k] = a*N[k–1] mod b a и b – взаимно простые. b удобнее всего брать 2^(8*m) и остаток от деления брать отбрасыванием срарших байтов. Конкретный пример (взятый не от балды): a=5^17, m=5. [quote=Надир] под управлением генератором я имел ввиду возмлжность задавать генератору следующее режимы: [/quote] При методе из абзаца выше все эти режимы «на ладошке». А можно и встроенный (в любом языке) взять и, если язык не позволяет явно инициализировать генератор заданным числом, то можно раскопать, по каким адресам N предыдущее хранится. | |
| 72
- 27.02.2014 - 20:37
|
[quote=Дюша;34334720](взятый не от балды): a=5^17, m=5 [/quote] А от Ольги Таусской. В вики есть совсем минимальный генератор. | |
| 73
- 01.03.2014 - 06:44
|
[quote=x_05772] В вики есть совсем минимальный генератор. [/quote] Как? Проще, чем одно единственное арифметическое действие?! | |
Интернет-форум Краснодарского края и Краснодара |
