Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 96
А покажите узор rand'а из линукса, и mt_randa из винды?
Windows 7, PHP/5.4.0RC5, mt_rand
habrastorage.org/storage2/b41/ba3/1fb/b41ba31fbf1ed595872be8117a958617.png
CentOS 5, PHP/5.3.5, rand
habrastorage.org/storage2/2ae/e33/1d5/2aee331d5dd716599fd4571211c2e7e9.png
CentOS 5, PHP/5.3.5, mt_rand
habrastorage.org/storage2/663/16a/8cd/66316a8cda37915ca93fc71fb3da2c7b.png
К сожалению на винде нет PHP/5.3.5, но думаю картина сильно отличаться не будет
habrastorage.org/storage2/b41/ba3/1fb/b41ba31fbf1ed595872be8117a958617.png
CentOS 5, PHP/5.3.5, rand
habrastorage.org/storage2/2ae/e33/1d5/2aee331d5dd716599fd4571211c2e7e9.png
CentOS 5, PHP/5.3.5, mt_rand
habrastorage.org/storage2/663/16a/8cd/66316a8cda37915ca93fc71fb3da2c7b.png
К сожалению на винде нет PHP/5.3.5, но думаю картина сильно отличаться не будет
В двух измерениях, оно выглядит не так уж и плохо, но это мало о чём говорит, скорее просто как иллюстрации интересного подхода к исследованиям случайных и не очень числовых последовательностей.
На практике приходится статистическими методами рассматривать исследуемые последовательности более чем трёх измерениях.
На практике приходится статистическими методами рассматривать исследуемые последовательности более чем трёх измерениях.
ИМХО, случайность — весьма относительное понятие. Я, конечно, не знаток теории вероятности (как, впрочем, и более близких к теме дисциплин, которые, к сожалению, я назвать сейчас не смогу), но я считаю, что абсолютного хаоса (т.е. чего-то, что не подчиняется никаким законам вообще) не существует — есть только плохо изученные системы. А посему терминологическое разделение генераторов чисел на «случайные» и «псевдослучайные» весьма надуманно, ибо «настоящих» случайных чисел не существует. Даже если вас попросить назвать любое число, то оно, каким бы случайным не казалось на первый взгляд, все равно будет зависеть от вашего прошлого опыта и вашего текущего состояния (а может, и еще от чего-то), но вот обнаружить все эти закономерности и попробовать предугадать ваше случайное число может оказаться чересчур сложной задачей. Впрочем, у генераторов случайных чисел есть и более объективные оценки, только вот классификацию осталось придумать (если она вообще нужна).
P.S. Проще говоря, ГСЧ отличается от ГПСЧ точно так же, как «много» отличается от «мало» — разница более-менее понятна, но вот четких границ нет и никогда не было, и на самом деле эти понятия не абсолютные, а связанные с какими-то прошлыми событиями и впечатлениями (например, вы увидели 100500 человек на площади, вас так или иначе впечатлила эта толпа, и теперь все, что хотя бы приблизительно похоже на эту толпу, является «много»; то же самое и с приставкой «псевдо» — последовательность символов «12345» для вас естественно неслучайна (притом, что следующим символом может быть как «6», так и «9», и "%"), а последовательность «19735» случайна до тех пор, пока вы не взглянете на блок цифровых клавиш).
P.S. Проще говоря, ГСЧ отличается от ГПСЧ точно так же, как «много» отличается от «мало» — разница более-менее понятна, но вот четких границ нет и никогда не было, и на самом деле эти понятия не абсолютные, а связанные с какими-то прошлыми событиями и впечатлениями (например, вы увидели 100500 человек на площади, вас так или иначе впечатлила эта толпа, и теперь все, что хотя бы приблизительно похоже на эту толпу, является «много»; то же самое и с приставкой «псевдо» — последовательность символов «12345» для вас естественно неслучайна (притом, что следующим символом может быть как «6», так и «9», и "%"), а последовательность «19735» случайна до тех пор, пока вы не взглянете на блок цифровых клавиш).
Кстати Фрейд, в «психопатологии обыденной жизни» написал отдельную главу о том, что случайные(выдуманные человеком) числа, совсем не такие уж случайные.
В классической физике действительно вероятность появляется из-за сложности систем и невозможности абсолютно точно задать начальные условия.
Но в квантовой механике случайность принципиальна, неустранима. Вычислить можно только вероятность того или иного результата измерения.
Но в квантовой механике случайность принципиальна, неустранима. Вычислить можно только вероятность того или иного результата измерения.
Верно. И надо по аналогии с flac'ом для аудиофилов сделать квантовый генератор истинно случайных чисел для рандомофилов.
Вы не поверите — он есть.
Я про это и говорил. Наш объем знаний представляет собой некоторое облако, края которого размыты, и что за ними находится, неизвестно. Мы не знаем ни абсолютного состава вещества (наименьшей частицы, как минимум — БАК не зря построили, и физики ломают головы не от нечего делать, а потому что просто так закономерность не выявишь даже с учетом всех текущих познаний), ни каким образом появилась Вселенная (да хотя бы что за границами, до которых не дотягиваются наши высокотехнологичные телескопы и тому подобная техника), ни других подобных далеких/глубоких областей. На текущий день наши знания не конечны, мир изучен не полностью, а значит, что сказать «оно работает именно так и никак иначе» мы можем далеко не про все его объекты — только лишь «скорее всего, оно будет так и так, но может и вот так». А это и есть вероятность (хаос, в какой-то мере), возникшая из-за «недоизученности» системы.
Наименьшей частицы? Это смотря какой теории вы приверженец. Согласно Стандартной модели, осталось найти лишь бозон Хиггса — и все частицы будут известны (всего предсказано 24 фундаментальные частицы). По состоянию на конец XX века все предсказания Стандартной модели подтверждались экспериментально, иногда с очень высокой точностью в миллионные доли процента. Наименьшей бесструктурной субчастицей сегодня считается кварк (в 20 тыс. раз меньше протона).
Каким образом появилась Вселенная? Наука дает нам вполне разумные (не интуитивные, но логичные, фальсифицируемые и имеющие веские доводы в их пользу) варианты развития событий. Доминирующая теория в данном космологическом направлении — теория Большого взрыва. Веский довод в пользу теории — анизотропия реликтового излучения. Заинтересованные читают/смотрят что-нибудь из Хокинга/Пенроуза. Хотя если честно, относительно Вселенной ещё много вопросов.
Мы знаем гораздо больше, чем кажется на первый взгляд. Просто мы не задумываемся о том, что знаем; но иногда готовы на всё, чтобы узнать то, чего не знаем. Мир можно изучать бесконечно.
Каким образом появилась Вселенная? Наука дает нам вполне разумные (не интуитивные, но логичные, фальсифицируемые и имеющие веские доводы в их пользу) варианты развития событий. Доминирующая теория в данном космологическом направлении — теория Большого взрыва. Веский довод в пользу теории — анизотропия реликтового излучения. Заинтересованные читают/смотрят что-нибудь из Хокинга/Пенроуза. Хотя если честно, относительно Вселенной ещё много вопросов.
Мы знаем гораздо больше, чем кажется на первый взгляд. Просто мы не задумываемся о том, что знаем; но иногда готовы на всё, чтобы узнать то, чего не знаем. Мир можно изучать бесконечно.
Мы знаем варианты и теории. Вот когда докажем, тогда и будем знать наверняка, и вот тогда хаоса (магии, НЕХ и прочей нечисти) будет меньше, а мы сможем влиять на мир бОльшим образом. До следующего несоответствия с реальностью (^_^)
Мир, возможно, непознаваем. Всё, что мы пока можем — пользоваться какой-то теорией, пока нет лучшей.
Формально, наука вообще не идет по пути «познания», причем уже очень давно. Она идет по пути «описания» и критерием правильности считается «предсказание».
Некая дыра в этом вопросе появилась только в последнее время, когда результаты предсказания двух разных теорий иногда сравниваются статистически и, следовательно, строго говоря ни одна из них не может считаться истиной. Точнее она считается «статистической истиной». Это смущает, но учитывая статистический характер изучаемого предмета (например поведения частиц микромира) считается приемлемым. Однако, это не истина. К сожалению.
Некая дыра в этом вопросе появилась только в последнее время, когда результаты предсказания двух разных теорий иногда сравниваются статистически и, следовательно, строго говоря ни одна из них не может считаться истиной. Точнее она считается «статистической истиной». Это смущает, но учитывая статистический характер изучаемого предмета (например поведения частиц микромира) считается приемлемым. Однако, это не истина. К сожалению.
Напомню вам, что стандартная модель несовместима с гравитацией (ОТО), то есть она в принципе не может претендовать на место теории, описывающей все фундаментальные законы.
Природа вещества ведь не изучена окончательно. Вполне возможно, что «случайность» в квантовой механике — это следствие неизученных пока неслучайных процессов, происходящих на более глубинном уровне. Может выяснится, что это и не случайность вовсе.
Тогда это проявлялось бы в экспериментах. См. неравенства Белла.
Из нарушения неравенств Белла следует лишь то, что некоторое измеряемое свойство квантовой частицы появляется у этой частицы только в момент измерения, а не является свойством этой частицы, присущим ей до измерения. Но из нарушения неравенств Белла нельзя сделать вывод, что в момент измерения мы получаем определенный результат лишь благодаря случайности, а не благодаря каким-то другим неизвестным пока неслучайным свойствам материи.
Т.е. доказано пока только нарушение локального реализма, а не то, что в момент измерения мы получаем гарантировано случайные результаты.
Т.е. доказано пока только нарушение локального реализма, а не то, что в момент измерения мы получаем гарантировано случайные результаты.
Согласно одному из определений (сорри не помню чье) случайность — мера нашего незнания процесса. Т.е. вы попали в десятку.
Вообще по поводу определения понятия «вероятность» споры ведутся очень давно, еще Колмогоров начал. А именно, понятие вероятности, как отношения количества «успехов» к общему количеству, на практике часто неприменимо, либо дает абсудный результат. Класич. пример — вероятность любого исторического события. Она неопределима, т.к. у нас нет «общего количества». Даже математически оно условно, например, вероятность попадания брошенной на бесконечную плоскость точки равна нулю (размер точки/размер бесконечности). Т.е. использование его для описания как «физических», так и «математических» процессов требует каких-то доп. ограничений природа которых не всегда ясна.
Чем тогда занимается наука? Содержанием армии ученых, надо полагать.
Вообще по поводу определения понятия «вероятность» споры ведутся очень давно, еще Колмогоров начал. А именно, понятие вероятности, как отношения количества «успехов» к общему количеству, на практике часто неприменимо, либо дает абсудный результат. Класич. пример — вероятность любого исторического события. Она неопределима, т.к. у нас нет «общего количества». Даже математически оно условно, например, вероятность попадания брошенной на бесконечную плоскость точки равна нулю (размер точки/размер бесконечности). Т.е. использование его для описания как «физических», так и «математических» процессов требует каких-то доп. ограничений природа которых не всегда ясна.
Чем тогда занимается наука? Содержанием армии ученых, надо полагать.
как отношения количества «успехов» к общему количеству
эт вообще не так, там используется понятие предела отношения, что несколько иное по сравнению с тем, что написали вы. + в математике в определениях всегда даются точное описание и говорится с какими оговорками это можно применять на практике.
например, вероятность попадания брошенной на бесконечную плоскость точки равна нулю (размер точки/размер бесконечности).
А что вас здесь не устраивает? Я вам даже больше скажу, кидание точки на отрезок [0,1] тоже даст вероятность попадания в конкретное значение = 0. И это абсолютная правда, нет тут никакого «противоречия» или «мистики»
Я как физик не согласен :)
Вопрос о том, существует ли случайность в реальности, — это вопрос о том, насколько результаты экспериментов и наблюдений соответствуют моделям, использующим понятие случайности. И он должен решаться на эксперименте.
Метод исследования в философии — это рассуждение. А с помощью одних рассуждений нельзя нельзя понять, реальна ли случайность.
Вопрос о том, существует ли случайность в реальности, — это вопрос о том, насколько результаты экспериментов и наблюдений соответствуют моделям, использующим понятие случайности. И он должен решаться на эксперименте.
Метод исследования в философии — это рассуждение. А с помощью одних рассуждений нельзя нельзя понять, реальна ли случайность.
Я так понял, что люди сделали следующим образом: взяли некоторую фигню, назвали ее случайностью, приписали ей с помощью аксиом (а потом уже теорем и прочего) свойства, характеристики и прочая, и теперь применяют это понятие на практике. Безусловно, в таком случае «случайность» существует, ибо есть статистические данные, удовлетворяющие всяким распределениям etc. И оно даже имеет смысл, ибо с помощью этого можно описывать системы, о которых мы не знаем, и, в принципе, работать с ними (получать какой-либо результат). Однако я говорю не про частную случайность (инструмент математики), а про абсолютную (всемирный хаос), некоторый объект, который ничему не подчиняется.
Мдя, походу мы начинаем говорить о разных вещах, вот я и путаюсь (-_-)
Мдя, походу мы начинаем говорить о разных вещах, вот я и путаюсь (-_-)
Мы в любом случае используем и эксперимент, и рассуждение — с помощью первого мы получаем более-менее объективные данные о реальности, а с помощью второго их анализируем, систематизируем и синтезируем новые знания. В конце концов, решение о том, насколько сильная погрешность эксперимента все-таки позволит нам считать, что оно соответствует модели, выносится уже в процессе рассуждения (т.к. у нас еще нет объективных данных о погрешностях, чтобы сравнить с ними — мы их и пытаемся получить, чтобы впоследствии работать с ними и улучшать).
На 100% сказать нельзя, но всё же это лучше, чем философствовать. Так хоть можно отсечь заведомо неправильные варианты.
На деле оно так и происходит, но получается, что другие (то есть философы) слабо разбираются в современных направлениях исследований, поэтому особого смысла в такой их деятельности нет.
На деле оно так и происходит, но получается, что другие (то есть философы) слабо разбираются в современных направлениях исследований, поэтому особого смысла в такой их деятельности нет.
Тут годится ответ Хокинга — «хорошая» теория описывает большой круг событий, «плохая» — малый. Но и та и другая, какой бы широкий круг она не предсказывала, не являются «истиной» в полном смысле.
Особенно учитывая что критерия «истинности» не существует.
Математически? Он как раз существует. Это выполнения ряда оговоренных условий/аксиом. Физически? Мы тоже должны ограничить/сформулировать круг понятий и в этом поле вполне можем оказаться абсолютно правы.
К сожалению.
К сожалению.
Математически? Истинность? При том, что непротиворечивость аксиоматики ZF, лежащей в основе всей современной математики не только не доказана, но и недоказуема в принципе? О какой вообще истинности можно говорить? Фактически, вся математика построена на вере непонятно во что.
Вы говорите о физическом смысле математических понятий. Аксиома (или набор аксиом) только задает абстрактное поле для построения теорий. Отрицание аксиомы также задает некое пространство теорий. Истинны они в физическом мире или нет, не имеет никакого значения.
Мне кажется (я бы не рискнул взяться это обосновывать) что с физикой дело обстоит примерно также. Я именно это хотел сказать. Мы тоже формулируем множество элементарных понятий, имеющих примитивно семантическую природу, как скажем «энтропия» или «энтальпия» и на основе этого множества строим некое пространство, потом накладываем его на «реальность» и по количеству отличий принимаем верна теория или нет.
Я бы сказал, что это дурацкая процедура, в ее основе лежит логическая ошибка и развивая процедуру мы также развиваем ошибку.
Мне кажется (я бы не рискнул взяться это обосновывать) что с физикой дело обстоит примерно также. Я именно это хотел сказать. Мы тоже формулируем множество элементарных понятий, имеющих примитивно семантическую природу, как скажем «энтропия» или «энтальпия» и на основе этого множества строим некое пространство, потом накладываем его на «реальность» и по количеству отличий принимаем верна теория или нет.
Я бы сказал, что это дурацкая процедура, в ее основе лежит логическая ошибка и развивая процедуру мы также развиваем ошибку.
Я говорю о чисто математическом смысле. Утвержение истинно, если оно следует из набора аксиом. Но если этот набор противоречив (как случилось, например, с наивной теорией множеств), то истинным оказывается любое утверждение. Поэтому, если наша исходная аксиоматика может оказаться противоречивой, то мы можем строить сколь угодно большое дерево утверждений, следующих из этой аксиоматики, пока не наткнемся на какой-нибудь парадокс. После чего понимаем, что понятие «истинности» обязано измениться, и вся предыдущая математика нуждается в пересмотре.
Да, и по поводу 100%. Это означает вероятность успеха теории = 1. И это же означает, что вы внутренне готовы оценивать верность некой теории по степени вероятности ее предсказаний. Согласитесь, это несколько странно.
Возможно, вы хотели сказать, что «модель» верна абсолютно. Это очень смело, но — возможно. Однако, соответствие физического мира математическим правилам в общем случае не очевидно. Это должно обсуждаться в каждом конкретном случае отдельно.
Возможно, вы хотели сказать, что «модель» верна абсолютно. Это очень смело, но — возможно. Однако, соответствие физического мира математическим правилам в общем случае не очевидно. Это должно обсуждаться в каждом конкретном случае отдельно.
А вы точно математик? Математик знает что эта штука называется «теория вероятностей», именно во множественном числе, а за словосочетание «теория вероятности» может и побить.
Вы не филолог случайно? Обычно люди не занимающиеся точными науками склонны выискивать какие-то парадоксы, «неточности» и прочую глубинную ерунду в устоявшихся основах этих наук :)
Я не хочу сказать, что вы не правы, но и то что вы сказали — особой практической пользы не имеет. Случайность для математиков — никакое не относительное понятие. Любую случайную последовательность можно подвергнуть различным тестам — проверке на монотонность, взаимонезависимость, равномерность распределения, постороить автокорлеляционную функцию (кстати она лучше всего показывает недостатки псевдослучаных последовательностей).
Каждый из этих тестов даст вполне ощуитиму числовую характеристику «случайности» этих чисел. Например, если взять случайную последовательность 12345, то она будет менее «случайной», чем 19735. Если взять результат функции rand() и результат ГНСЧ, то точно также показатели «случайности» у ГНСЧ будут выше. Вот и все, к чему излишнее философствование? :)
Я не хочу сказать, что вы не правы, но и то что вы сказали — особой практической пользы не имеет. Случайность для математиков — никакое не относительное понятие. Любую случайную последовательность можно подвергнуть различным тестам — проверке на монотонность, взаимонезависимость, равномерность распределения, постороить автокорлеляционную функцию (кстати она лучше всего показывает недостатки псевдослучаных последовательностей).
Каждый из этих тестов даст вполне ощуитиму числовую характеристику «случайности» этих чисел. Например, если взять случайную последовательность 12345, то она будет менее «случайной», чем 19735. Если взять результат функции rand() и результат ГНСЧ, то точно также показатели «случайности» у ГНСЧ будут выше. Вот и все, к чему излишнее философствование? :)
Нет, я по большей части все-таки точных наук ремесленник, хотя подобные измышления мне не чужды. Программист я, но одно время занимавшийся теорией архитектуры программного обеспечения (громко сказано — на самом деле искал точку, после которой стоит остановиться дробить и абстрагироваться, а также способы определения границ расширяемости «надо учесть, а то вдруг»).
«Устоявшихся наук». Устояться-то они устоялись, но вот если копать глубже (чем сейчас народ и занимается), то есть шанс, что все эти устои потеряют ценность как дающие безумную погрешность. Шанс, правда, маленький — с гораздо большей вероятностью все останется на своих местах, как физика Ньютона, но с оговорками. Так что и физики ищут парадоксы «и прочую глубинную ерунду» ради того, чтобы понять наконец-то, а чегой-то оно двигается.
«Особой практической пользы не имеет». Я с вами согласен на 99,9(9)%. Тот бесконечно маленький процент состоит из тех людей, которые однажды, понадеявшись на ГСЧ на основе физических величин вроде уровня шума, уронят челюсти, когда увидят, что этот алгоритм был взломан (а, по сути, взломали природу). Сейчас это больше из области фантастики, чем реальности, но кто знает, до чего додумаются физики… А так это действительно всего лишь мое ИМХО, не претендующее на то, чтобы приносить пользу.
Впрочем, я рад, что у нас есть возможность в процессе подобных дискуссий систематизировать все наши «разнообразные знания» и продвинуться дальше (^_^) Глядишь, сейчас чего-нибудь да изобретем…
«Устоявшихся наук». Устояться-то они устоялись, но вот если копать глубже (чем сейчас народ и занимается), то есть шанс, что все эти устои потеряют ценность как дающие безумную погрешность. Шанс, правда, маленький — с гораздо большей вероятностью все останется на своих местах, как физика Ньютона, но с оговорками. Так что и физики ищут парадоксы «и прочую глубинную ерунду» ради того, чтобы понять наконец-то, а чегой-то оно двигается.
«Особой практической пользы не имеет». Я с вами согласен на 99,9(9)%. Тот бесконечно маленький процент состоит из тех людей, которые однажды, понадеявшись на ГСЧ на основе физических величин вроде уровня шума, уронят челюсти, когда увидят, что этот алгоритм был взломан (а, по сути, взломали природу). Сейчас это больше из области фантастики, чем реальности, но кто знает, до чего додумаются физики… А так это действительно всего лишь мое ИМХО, не претендующее на то, чтобы приносить пользу.
Впрочем, я рад, что у нас есть возможность в процессе подобных дискуссий систематизировать все наши «разнообразные знания» и продвинуться дальше (^_^) Глядишь, сейчас чего-нибудь да изобретем…
понадеявшись на ГСЧ на основе физических величин вроде уровня шума, уронят челюсти, когда увидят, что этот алгоритм был взломан
Хочу заметить что случаи взлома смарт карт использующих в качестве ГСЧ тепловые шумы уже наблюдались — их просто замораживали таким образом существенно снижая эту самую «случайность».
Разделение между ГСЧ и ГПСЧ весьма строгое. Основное отличие в том, что вывод ГПСЧ детерминирован, т.е. зная начальные условия повторим сколько угодно раз. В то время как, вывод ГСЧ может повториться в будущем только с исчезающе малой вероятностью повторения случайной последовательности.
Поэтому например для численных экспериментов (Монте-Карло и тд) удобнее использовать качественные ГПСЧ, тк возможность повторить последовательность иногда полезна.
Поэтому например для численных экспериментов (Монте-Карло и тд) удобнее использовать качественные ГПСЧ, тк возможность повторить последовательность иногда полезна.
Хм. Если мы каким-то невероятным образом восстановим состояние окружающей среды у аппаратного ГСЧ, использующего в качестве энтропии внешний источник, то мы получим тот же ГПСЧ. Следовательно, все ГСЧ — те же ГПСЧ, просто восстановить начальные условия мы не можем.
Возможно я плохо помню, но степень случайности любого цифрового ряда оценивается по вероятности появления отдельных членов этого ряда. Для 0 и 1 это должно быть 0.5
Т.е. никакого «строгого» различия тут не существует, это между 0.04999999 и 0.49999998.
И кроме того, результат будет очень сильно зависеть от представительности выборки, т.е чтобы получить доказательство вам придется взять бесконечный ряд результатов эксперимента, т.е. как раз то, где определение вероятности теряет смысл. Но, это уже другая история.
Т.е. никакого «строгого» различия тут не существует, это между 0.04999999 и 0.49999998.
И кроме того, результат будет очень сильно зависеть от представительности выборки, т.е чтобы получить доказательство вам придется взять бесконечный ряд результатов эксперимента, т.е. как раз то, где определение вероятности теряет смысл. Но, это уже другая история.
>Я, конечно, не знаток теории вероятности
На этой фразе нужно было и закончить…
Люди диссертации защищают, я магистерский диплом писал на эту тему, а оказывается «терминологическое разделение генераторов чисел на случайные и псевдослучайные весьма надуманно». И «классификацию осталось придумать». Может не стоит писать откровения про вещи, о которых не имеете ни малейшего представления?
На этой фразе нужно было и закончить…
Люди диссертации защищают, я магистерский диплом писал на эту тему, а оказывается «терминологическое разделение генераторов чисел на случайные и псевдослучайные весьма надуманно». И «классификацию осталось придумать». Может не стоит писать откровения про вещи, о которых не имеете ни малейшего представления?
Мои знания весьма поверхностны, не спорю. Я и пытаюсь определить, каким же конкретно образом можно сказать, что этот алгоритм (устройство) — ГСЧ, а этот — всего лишь ГПСЧ. Может быть, я чего-то не увидел, но я пока заметил только одно конкретное различие в комментарии выше. Надеюсь, что вы, как специалист, поможете разобраться в этом вопросе. Судя по вашим постам, вы не похожи на «умников» с автобусной остановки, которые на вопрос «а этот автобус меня довезет до МКАДа?» ржут и отвечают «да пошел ты в лес — во ущербный человек, даже карты Москвы наизусть не помнит!».
Абсолютно все, что генерируется алгоритмом (программным или аппаратным) — это ГПСЧ. Генераторы истинно случайных чисел основываются на физических эффектах, обычно квантовых.
Т.е. если ГПСЧ скормить в качестве входных данных некие постоянно меняющиеся данные (неважно, будь это уровень шума или timestamp — изменятся только качественные характеристики получаемого результата), то этот комплекс (ГПСЧ + внешние данные) станет называться ГСЧ?
P.S. Я вспомнил, к чему и о чем был тот первый комментарий (корень этой ветки). Он касался только «истинно случайных чисел» и физических явлений, на основе которых эти ИСЧ получаются. В принципе, это касается только физики (а не математики — своей «теорией вероятности» я ввел всех в заблуждение). Тут было несколько подветок комментариев, которые затронули случайные процессы в квантовой механике — в частности, я высказал теорию и про это, что на самом деле все закономерно, а случайности появляются из-за того, что мы эти закономерности не знаем. Что-то как-то я эту теорию (ни в коем случае не указание «как есть на самом деле», а всего лишь догадки) потянул не в ту сторону.
P.S. Я вспомнил, к чему и о чем был тот первый комментарий (корень этой ветки). Он касался только «истинно случайных чисел» и физических явлений, на основе которых эти ИСЧ получаются. В принципе, это касается только физики (а не математики — своей «теорией вероятности» я ввел всех в заблуждение). Тут было несколько подветок комментариев, которые затронули случайные процессы в квантовой механике — в частности, я высказал теорию и про это, что на самом деле все закономерно, а случайности появляются из-за того, что мы эти закономерности не знаем. Что-то как-то я эту теорию (ни в коем случае не указание «как есть на самом деле», а всего лишь догадки) потянул не в ту сторону.
Гейзенберг? Не, не слыхал…
Почему-то вспоминается анекдот
Заходят Вернер Гейзенберг, Курт Гёдель и Ноам Хомский в бар.
Гейзенберг смотрит по сторонам и говорит: «Поскольку здесь находимся мы втроём, и поскольку здесь бар, то это — наверняка анекдот. Однако, остаётся один вопрос — смешной он или нет?»
Гёдель на секунду задумывается и отвечает: «Ну, так как мы находимся внутри анекдота, мы не можем сказать, смешной он или нет. Чтобы это понять, нам нужно взглянуть на него снаружи».
Хомский смотрит на них и говорит: «Конечно же, он смешной. Вы просто неправильно его рассказываете.»
> Гейзенберг? Не, не слыхал…
Он известен под фамилией Гайзенберг.
Он известен под фамилией Гайзенберг.
Эти узоры показывают разницу не между ГСЧ и ГПСЧ, а между хорошим ГПСЧ и плохим. Генераторы случайных чисел обычно оценивают по двум показателям: статистическим характеристикам и детерменированности.
Cтатистические характеристики — это относительные частоты символов и подпоследовательностей, спектры распределения, линейная (не)зависимость подпоследовательностей — более сотни параметров (см. DIEHARD и NIST). За них отвечает алгоритм ГПСЧ.
Детерменированность показывает, насколько легко предсказать следующие символы последовательности, зная предыдущие. В идеале — должно быть невозможно. Для достижения этого применяются источники энтропии, обычно — аналоговые генераторы шума. Источник энтропии может иметь плохие статистические характеристики, они в дальнейшем улучшаются путем прогона данных через ГПСЧ.
Cтатистические характеристики — это относительные частоты символов и подпоследовательностей, спектры распределения, линейная (не)зависимость подпоследовательностей — более сотни параметров (см. DIEHARD и NIST). За них отвечает алгоритм ГПСЧ.
Детерменированность показывает, насколько легко предсказать следующие символы последовательности, зная предыдущие. В идеале — должно быть невозможно. Для достижения этого применяются источники энтропии, обычно — аналоговые генераторы шума. Источник энтропии может иметь плохие статистические характеристики, они в дальнейшем улучшаются путем прогона данных через ГПСЧ.
> только вот классификацию осталось придумать (если она вообще нужна).
Она уже есть и она нужна. На данных ГСЧ основана генерация ключей в распространенных криптоалгоритмах, т.е. если мы за приемлемый промежуток времени можем предсказать последовательность СЧ, то это делает алгоритм уязвимым.
Она уже есть и она нужна. На данных ГСЧ основана генерация ключей в распространенных криптоалгоритмах, т.е. если мы за приемлемый промежуток времени можем предсказать последовательность СЧ, то это делает алгоритм уязвимым.
Я имел в виду классификацию на основе объективных показателей, например, тех, что Ocelot привел в комментарии выше.
Если немного переврать ваши слова, то получается, что названия «генератор случайных чисел» и «генератор псевдослучайных чисел» взяты с потолка, и на самом деле они называются «генератор случайных чисел, который можно использовать в криптоалгоритмах» и «генератор случайных чисел, который использовать в криптоалгоритмах опасно». Я же предлагаю добавить конкретности, например, ГСЧ, который можно использовать в криптоалгоритмах с 99% уверенностью в том, что его не взломают, должен обладать такими-то характеристиками, а ГСЧ, который дает более-менее недетерменированные числа, но его можно использовать только для генерации shuffle-плейлистов, должен обладать такими-то характеристиками. При этом, если вам угодно, второй ГСЧ можно переобозвать как «ГПСЧ».
Насчет «если она вообще нужна». Можно потратить кучу времени и денег и в конце концов создать толстую-толстую спецификацию всевозможных ГСЧ, объединенных по классам в зависимости от их характеристик, но окупится ли она? Будут ли ей пользоваться другие, или это будет «классификация ради классификации»? В конце концов, люди до сих пор пользуются понятиями «много» и «мало», несмотря на то, что уже давно придуманы числа, понятия «больше»/«меньше» etc.
Если немного переврать ваши слова, то получается, что названия «генератор случайных чисел» и «генератор псевдослучайных чисел» взяты с потолка, и на самом деле они называются «генератор случайных чисел, который можно использовать в криптоалгоритмах» и «генератор случайных чисел, который использовать в криптоалгоритмах опасно». Я же предлагаю добавить конкретности, например, ГСЧ, который можно использовать в криптоалгоритмах с 99% уверенностью в том, что его не взломают, должен обладать такими-то характеристиками, а ГСЧ, который дает более-менее недетерменированные числа, но его можно использовать только для генерации shuffle-плейлистов, должен обладать такими-то характеристиками. При этом, если вам угодно, второй ГСЧ можно переобозвать как «ГПСЧ».
Насчет «если она вообще нужна». Можно потратить кучу времени и денег и в конце концов создать толстую-толстую спецификацию всевозможных ГСЧ, объединенных по классам в зависимости от их характеристик, но окупится ли она? Будут ли ей пользоваться другие, или это будет «классификация ради классификации»? В конце концов, люди до сих пор пользуются понятиями «много» и «мало», несмотря на то, что уже давно придуманы числа, понятия «больше»/«меньше» etc.
«генератор случайных чисел, который можно использовать в криптоалгоритмах» называется «криптостойкий ГСЧ»
А, ясно. В принципе, согласно той же википедии нечто вроде спецификации все-же есть — ru.wikipedia.org/wiki/%D0%93%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D1%82%D0%BE%D1%80_%D0%BF%D1%81%D0%B5%D0%B2%D0%B4%D0%BE%D1%81%D0%BB%D1%83%D1%87%D0%B0%D0%B9%D0%BD%D1%8B%D1%85_%D1%87%D0%B8%D1%81%D0%B5%D0%BB#ANSI_X9.17
я что-то вообще не понял смысла со статьи. Ваша задача была показать, как рисовать картинку, которая генерируется функцией rand()? Или сказать, что случайные числа на компьютере не случайны? ИМХО — кто это читает, практически все это знают. Простой аналог функции rand я писал даже на экселе (даже несмотря на то, что там есть встроенная функция).
Статья была бы намного ценнее, если были бы приведены сами алгоритмы генерации случайных чисел (хотя бы простейшие), а еще лучше — функции перевода случайных равномерно распределенных чисел к нормальному (Гауссовскому) распределению.
Статья была бы намного ценнее, если были бы приведены сами алгоритмы генерации случайных чисел (хотя бы простейшие), а еще лучше — функции перевода случайных равномерно распределенных чисел к нормальному (Гауссовскому) распределению.
Спасибо за отзыв.
Я перевёл статью, которая показалась мне интересной из-за наглядности.
Еще я обнаружил, что отличный сайт random.org на Хабре упоминался один раз в 2009 году.
И разумеется хотелось карму поднять :)
Я перевёл статью, которая показалась мне интересной из-за наглядности.
Еще я обнаружил, что отличный сайт random.org на Хабре упоминался один раз в 2009 году.
И разумеется хотелось карму поднять :)
А в чём сложность приводить равномерно распределённые случайные величины к гаусовскому распределению?
>Или сказать, что случайные числа на компьютере не случайны?
Думаю, скорее показать, что несмотря на то, что на дворе второе десятилетие двадцать первого века, в некоторых системах в головах ещё примерно 1984-й год (это я вспоминая какие красивые узоры рисовал ГПСЧ спектрума).
>ИМХО — кто это читает, практически все это знают.
Безусловно. Но разные ГПСЧ могут очень сильно различаться по качеству. Я вот, честно сказать, был почти уверен, что _настолько_ плохих ГПСЧ в настоящее время быть не должно. Разработчики же вендов и пехапе в очередной раз неприятно удивили…
>Статья была бы намного ценнее, если были бы приведены сами алгоритмы генерации случайных чисел (хотя бы простейшие), а еще лучше — функции перевода случайных равномерно распределенных чисел к нормальному (Гауссовскому) распределению.
Зачем? Это-то как раз довольно банально и описано в любом букваре. А вот наглядная демонстрация дырок в головах некоторых разработчиков хоть и ширпотребовских, но, всё ещё, довольно распространённых систем заставляет задуматься.
Думаю, скорее показать, что несмотря на то, что на дворе второе десятилетие двадцать первого века, в некоторых системах в головах ещё примерно 1984-й год (это я вспоминая какие красивые узоры рисовал ГПСЧ спектрума).
>ИМХО — кто это читает, практически все это знают.
Безусловно. Но разные ГПСЧ могут очень сильно различаться по качеству. Я вот, честно сказать, был почти уверен, что _настолько_ плохих ГПСЧ в настоящее время быть не должно. Разработчики же вендов и пехапе в очередной раз неприятно удивили…
>Статья была бы намного ценнее, если были бы приведены сами алгоритмы генерации случайных чисел (хотя бы простейшие), а еще лучше — функции перевода случайных равномерно распределенных чисел к нормальному (Гауссовскому) распределению.
Зачем? Это-то как раз довольно банально и описано в любом букваре. А вот наглядная демонстрация дырок в головах некоторых разработчиков хоть и ширпотребовских, но, всё ещё, довольно распространённых систем заставляет задуматься.
В соём посте, про аппаратный генератор случайных чисел habrahabr.ru/blogs/DIY/133320/
Я приводил гистограмму распределения случайных чисел файла /dev/random
На мой взгляд она много нагляднее белого шума. А вообще есть алгоритмы, вычисляющие корреляции. На картинке, где проявился узор на лицо корреляция соседних случайных велечин.
Я приводил гистограмму распределения случайных чисел файла /dev/random
На мой взгляд она много нагляднее белого шума. А вообще есть алгоритмы, вычисляющие корреляции. На картинке, где проявился узор на лицо корреляция соседних случайных велечин.
Для того чтобы рисовать картинки, или генерировать пользователям пароли, из генераторов псевдослучайных чисел можно использовать хоть int myrand(){ return 4; }, для тех же случаев когда нужен действительно высокий уровень случайности (к примеру генерация ключевых данных во избежание коллизий), никакой mt_rand не спасёт. Только аппаратные решения. Использование физических процессов для получения случайных чисел сводят на нет возможность воспроизвести последовательность злоумышленнику. Что касается random.org, то его можно разве что как развлечение использовать. Сгенерированные там данные могут оказаться в чьих угодно руках.
Генерировать случайные числа можно по-разному; а еще немаловажно инициализировать генератор, чтобы не получать слишком уж явных корреляций.
Так вот кто будет производить АТ-АТ…
Стройте картинку не 512*512 а по модулям двух разных простых чисел — 521*523 например
Помню как-то молодой был (лет 10-12 было, тогда ещё PC не было, только на спектрумском бейсике баловался, немного ASM черпал) любил рисовать на экране случайными числами… Помню команда RND медленная была, я в качестве случайного генератора использовал магнитофонный порт. Думаю и сейчас вполне легко можно написать генератор который бы с микрофонного входа звуковухи брал шум. (или даже с самого микрофона) главное как нибудь хешировать выход, потому что шумы всегда «похожие» (если взять WAV и переписать ему заголовок на BMP то там будут или какие нибудь клетки/полосы или ещё чего нибудь, не проверял, но думаю так...)
Плохонький там шум нонче: в хороших звуковушках, все-таки, стоят шумоподавляющие фильтры (аппаратные). А вот если бы поставить АЦП на вход блока питания, можно было бы получить очень даже неплохой генератор псевдослучайных чисел…
Хороший или плохой но он есть… Вопрос лишь как убрать из него характерные черты и сделать «непредсказуемым»
нормальный там шум))
habrahabr.ru/blogs/python/62237/
habrahabr.ru/blogs/python/62237/
У меня более-менее приличный шум (при экспериментировании с несколькими звуковушками) получался лишь в случае с откровенно жуткой звуковушкой (не помню названия, на работе смогу глянуть) за ~100р и с парой встроенных (но с ними все ясно и так).
Количество (уровень) шума особой роли не играет. Главное чтобы младшие биты не обрезались или еще как-то обрабатывались. В любом АЦП есть случайный шум (а 24-битные так вообще), дальше дело техники. Главное не жадничать, брать только младшие биты, правильно обрабатывать и контролировать результат.
> В любом АЦП есть случайный шум (а 24-битные так вообще)
К сожалению, ни одной 24-битной звуковушки мне в руки не попадалось. Лучшее, что нашел, было 14-битным (при заявленных 24). Но шум там был коррелированным.
К сожалению, ни одной 24-битной звуковушки мне в руки не попадалось. Лучшее, что нашел, было 14-битным (при заявленных 24). Но шум там был коррелированным.
Поэтому я и написал, что надо правильно его готовить)
Шум может (и скорей всего будет) засорен всякой ерундой типа фоновых 50 Гц от питания, артефактов дискретизации, «улучшайзеров» и тд. Это всего лишь затрудняет оценку количества энтропии, но не делает его бесполезным.
Главное что в нём есть случайная компонента и есть алгоритмы которые позволяют её «отмыть», чтобы померить статистические характеристики.
Шум может (и скорей всего будет) засорен всякой ерундой типа фоновых 50 Гц от питания, артефактов дискретизации, «улучшайзеров» и тд. Это всего лишь затрудняет оценку количества энтропии, но не делает его бесполезным.
Главное что в нём есть случайная компонента и есть алгоритмы которые позволяют её «отмыть», чтобы померить статистические характеристики.
Код можно сделать не привязанным к графической библиотеке языка если генерировать картинку в формате PBM, вот так будет выглядеть код на Perl:
если его выполнить
то получим готовую картинку (в данном случае без узоров), такой алгоритм элементарно переписать на любой язык для сравнения функций генерации псевдослучайных чисел.
#!/usr/bin/perl -w
use strict;
my $dimension = 512;
print 'P1', $/;
print "$dimension $dimension$/";
foreach my $y (1..$dimension) {
foreach my $y (1..$dimension) {
print rand() >= 0.5 ? 1 : 0;
}
print $/;
}если его выполнить
perl rand-map.pl > rand-map.pbmто получим готовую картинку (в данном случае без узоров), такой алгоритм элементарно переписать на любой язык для сравнения функций генерации псевдослучайных чисел.
Тоже хотел подобное написать (типа вовсе не обязательно GD использовать и прочие танцы)
Только у меня был пример в BMP на РНР
pastebin.com/h4QdxXgc (PBM ещё проще)
Только у меня был пример в BMP на РНР
pastebin.com/h4QdxXgc (PBM ещё проще)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Псевдослучайно vs. По-настоящему Случайно