Информация

Дата основания
2008
Местоположение
Россия
Сайт
www.securitycode.ru
Численность
201–500 человек
Дата регистрации

Блог на Хабре

Обновить
Комментарии 13
Ай-ай-ай, воровать тележки из супермаркетов нехорошо:
Скриншот
image
Но до меня они еще не доехали :(
А вы хорошо себя вели в этом году? Говорят, тележки приезжают только к послушным мальчикам и девочкам.
предупрежать надо, что X конечно.
с колмогоровской сложностью — не совсем понятно. если взять реализацию как есть — бесконечную, то, я думаю, вообще невозможно построить её (реализации) алгоритмическое описание.
если же взять префикс реализации, то существует язык в котором его описание имеет длину 2.
Колмогоровская сложность — очень теоретическая штука. Например, она невычислима…
То что вы написали про длину 2 — верно, но нету такого «языка программирования», для которого все строки длины N можно описать программами длины 2. То есть КС есть смысл рассматривать на совокупности строк, а не на одной конкретной.
Наверное это наивно, но я думал, что с появлением теорий хаоса, бифуркаций проблема с генерацией случайных последовательностей чисел вообще снимается… Какое-нибудь логистическое преобразование или аттрактор Лоренца разве не позволяют генерить совершенно непредсказуемые последовательности? Интересно было бы их протестировать с помощью методов, описанных в статье.
У компьютера (цифрового) конечное число состояний и переход из одного в другое строго детерминирован. Когда-нибудь мы получим такое же состояние как уже было и все следующие будут предсказуемыми, последовательность зациклится, станет периодической, а значит по определению не будет случайной.

Чисто вычислительными методами на цифровом компьютере случайную последовательность точно не получить. Максимум, можно применять вычислительные преобразования к внешним источникам энтропии, но если они реально случайные, то нет смысла и применять преобразования.
Да, вы правы, я туплю… Вот, например, логистическое отображение:

function lm_rand(x0, r, n) {
  var x = x0;
  for (var i = 0; i < n; i++) {
    x = r * x * (1 - x);
  }
  return x;
}

При малейших изменениях параметров результат конечно сильно меняется:
lm_rand(0.5, 3.9, 100) = 0.9546
lm_rand(0.49, 3.9, 100) = 0.6160
lm_rand(0.5, 3.9, 101) = 0.1689
lm_rand(0.5, 3.91, 100) = 0.8881

Но если запускать его с теми же самыми параметрами, то результат будет один и тот же.

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

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


Мелко плаваете — миллион. Как насчёт 2^64 (грубо — адресное пространство 64-бит процессоров) значений, например?
Хотел написать, что вы не правы, что хаос на то и хаос, что там нет никаких периодов. А человеку, который их найдёт дадут Нобелевскую премию. Но, блин, компьютеры, ведь, действительно дискретные. Если длина последовательности сравнима с точностью вычислений, то логистическое отображение однозначно начнёт повторяться. Например, если 64-битная точность вычислений, то на последовательности 2^64 однозначно будут периоды.

Кому интересно логистическое отображение, для теста нагенерил случайных чисел в Excel. Там две последовательности по 5000 значений. В них период, очевидно, не нашёл. Но на более длинных последовательностях он будет из-за ограниченной точности вычислений.

Хотя, если добавить в вычисления хотя бы текущее время, я думаю периодов можно избежать.

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

Это конечно звучит безумно. У программистов всё должно быть абсолютно детерминировано. Но, по-моему, немного хаоса тут не помешало бы.
Ну, Интел точно начала встраивать. Другое дело, насколько мы можем доверять Интел в этом вопросе.
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.