Что значит рандомное число
Что значит «рандомно» в интернет-сленге?
Современный интернет-сленг ежедневно пополняется новыми словами и выражениями. Они заимствуются из других языков и профессиональных жаргонизмов, подстраиваются под нужды пользователей сети и прочно закрепляются в их речи. Одним из таких терминов является слово «рандомно». Что оно обозначает? Откуда появилось и как используется сейчас?
Значение и происхождение
Термин «рандомно» произошел от английского random (случайный, произвольный, хаотичный). Внедрился в русское интернет-сообщество благодаря геймерскому комьюнити.
Еще в «древних» пиксельных RPG присутствовал элемент случайности в выпадении лута после поединков. В современных РПГ и ММОРПГ этот принцип сохраняется.
Инди RPG Job Hunt Heroes. Момент выпадения лута
Кейсы Counter-Strike:Global Offensive
В некоторых играх можно выбрать рандомный мир для выживания или персонажа для сражения со случайным набором характеристик. Это позволяет игроку прокачивать свои умения в любых условиях.
Также считается, что слово «рандомно» пришло из языка программирования, а точнее, произошло от функции random (случайная последовательность чисел).
Современное использования термина
Выражение давно используется за пределами гейм-комьюнити и среды программирования. Сейчас его употребляют повсеместно. Например, термин «рандомно» применяется во время розыгрыша каких-либо предметов в соцсетях (от стикеров Вконтакте до автомобилей). Так, во время раздачи призов выбирается рандомный победитель с помощью генератора чисел. Таких сервисов в интернете много, их называют рандомайзерами. Принцип пользования очень прост. Каждому участнику конкурса присваивается индивидуальный номер. В рандомайзер вводится общее число участников, после чего программа выдает рандомное число. Победителем считается человек, чей конкурсный номер совпал с числом, выданным рандомайзером.
Рандомайзер
Это не исключительный вариант использования термина. Слово настолько прижилось, что стало полноправным синонимом слова «случайно». Оно используется и за пределами сети.
Несмотря на давность появления, «рандомно» используется и по сей день. Употребление термина популярно как среди молодежи, так и среди взрослых.
С происхождением и использованием сленговых выражений, таких как: рофлю, страйк, коннект, – можно ознакомиться в других статьях.
Алгоритмы рандома
В этой статье вы увидите самые разнообразные велосипеды алгоритмы для генерации случайных чисел.
Про что статья
C++ rand
Первое что узнаёт начинающий программист С++ по теме получения рандома — функция rand, которая генерирует случайное число в пределах от 0 и RAND_MAX. Константа RAND_MAX описана в файле stdlib.h и равна 32’767, но этом может быть не так, например в Linux (см. коммент). Если же rand() в вашем компиляторе генерирует числа в пределах 32’767 (0x7FFF) и вы хотите получить случайное число большого размера, то код ниже можно рассматривать как вариант решения этой проблемы:
Реализация функции rand в старом C была проста и имела следующий вид:
Данная реализация имела не очень хорошее распределение чисел и ныне в C++ улучшена. Так же стандартная библиотека C++ предлагает дополнительные способы получения случайного числа, о которых ниже.
С++11 STL random
Данный сорт рандома появился в C++11 и представляет из себя следующий набор классов: minstd_rand, mt19937, ranlux, knuth_b и разные их вариации.
Чтобы последовательность случайных чисел не повторялась при каждом запуске программы, задают «зерно» псевдослучайного генератора в виде текущего времени или, в случае с некоторыми ретро (и не только) играми — интервалы между нажатиями клавиш с клавиатуры/джойстика. Библиотека random же предлагает использовать std::random_device для получения зерна лучше чем от time(NULL), однако в случае с компилятором MinGW в Windows функция практически не работает так как надо. До сих пор…
Некоторые из алгоритмов в STL random могут работать быстрее чем rand(), но давать менее качественную последовательность случайных чисел.
PRNG — Pseudo-random Numbers Generator
Можете считать это название — синонимом линейного конгруэнтного метода. PRNG алгоритмы похожи на реализацию rand в C и отличаются лишь константами.
PRNG алгоритмы быстро работают и легки в реализации на многих языках, но не обладают большим периодом.
XorShift
Алгоритм имеющий множество вариаций отличающихся друг от друга периодом и используемыми регистрами. Подробности и разновидности XorShift’а можете посмотреть на Википедии или Хабре. Приведу один из вариантов с последовательностью 2 в 128-й степени.
Данный генератор очень хорош тем, что в нём вообще нет операций деления и умножения — это может быть полезно на процессорах и микроконтроллерах в которых нету ассемблерных инструкций деления/умножения (PIC16, Z80, 6502).
8-bit рандом в эмуляторе z26
Z26 это эмулятор старенькой приставки Atari2600, в коде которого можно обнаружить рандом ориентированный на работу с 1-байтовыми регистрами.
Однажды мне пришлось сделать реализацию этого алгоритма для z80:
Компактный рандом для Z80 от Joe Wingbermuehle
Если вам интересно написание программ под машины с зилогом, то представляю вашему вниманию алгоритм от Joe Wingbermuehle (работает только на зилоге):
Генератор рандома в DOOM
В исходниках игры Дум есть такой интересный файл под названием m_random.c (см. код), в котором описана функция «табличного» рандома, то есть там вообще нет никаких формул и магии с битовыми сдвигами.
Приведу более компактный код наглядно показывающий работу этой функции.
Конечно же это ни какой не рандом и последовательность случайных чисел легко предугадать даже на уровне интуиции в процессе игры, но работает всё это крайне быстро. Если вам не особо важна криптографическая стойкость и вы хотите что-то быстро генерирующее «типа-рандом», то эта функция для вас. Кстати в Quake3 рандом выглядит просто — rand()&0x7FFF.
RDRAND
Некоторые современные процессоры способны генерировать случайные числа с помощью одной ассемблерной команды — RDRAND. Для использования этой функции в C++ вы можете вручную прописать нужные инструкции ассемблерными вставками или же в GCC подключить файл immintrin.h и выбрать любую из вариаций функции _rdrandXX_step, где XX означает число бит в регистре и может быть равно 16, 32 или 64.
Концовка
Класс std::minstd_rand из библиотеки STL random работает быстрее обыкновенного rand() и может стать его альтернативной заменой, если вас не особо волнует длинна периода в minstd. Возможны различия в работе этих функций в Windows и Unix’ах.
Значение слова «рандомный»
рандо́мный
1. спец. жарг. случайный ◆ Правда, в новой модели конструкторы обещают внести элементы непредсказуемости, чтобы могла отказываться, ссылаясь на рандомные причины. Юрий Никитин, «Рассветники», 2015 г.
Делаем Карту слов лучше вместе
Привет! Меня зовут Лампобот, я компьютерная программа, которая помогает делать Карту слов. Я отлично умею считать, но пока плохо понимаю, как устроен ваш мир. Помоги мне разобраться!
Спасибо! Я стал чуточку лучше понимать мир эмоций.
Вопрос: центрирование — это что-то нейтральное, положительное или отрицательное?
Предложения со словом «рандомный»
Отправить комментарий
Дополнительно
Предложения со словом «рандомный»
– Рандомный выбор, не более.
Только что зарегистрированный игрок теперь попадал не в рандомный город, а в точку, приблизительно аналогичную той, что на земной карте соответствовала его населённому пункту.
Приватный ключ может быть представлен в виде сид (seed) фразы, которая представляет из себя рандомный набор слов, расположенных в определённом порядке.
Карта слов и выражений русского языка
Онлайн-тезаурус с возможностью поиска ассоциаций, синонимов, контекстных связей и примеров предложений к словам и выражениям русского языка.
Справочная информация по склонению имён существительных и прилагательных, спряжению глаголов, а также морфемному строению слов.
Сайт оснащён мощной системой поиска с поддержкой русской морфологии.
Случайные числа (random numbers)
Психологи часто пользуются С. ч. для решения разных задач. Напр., можно сформировать случайную выборку, нумеруя потенциальных испытуемых в совокупности, а затем отбирая на основе таблицы С. ч. реальных испытуемых для включения в ее состав. Такой случайный процесс гарантировал бы получение случайной (непредвзятой) выборки — необходимого, по существу, условия всех видов статистического анализа.
С. ч. тж могут использоваться для распределения испытуемых по группам (соответственно условиям) в эксперименте, для выбора уровней предъявления независимой переменной или для эмпирического построения выборочных распределений статистик путем случайного извлечения выборок из совокупности с известным распределением.
См. также Вероятность, Статистика в психологии
Смотреть что такое «Случайные числа (random numbers)» в других словарях:
СЛУЧАЙНЫЕ ЧИСЛА — (random numbers) см. Выборочная совокупность и выборка … Большой толковый социологический словарь
Псевдослучайные числа — Генератор псевдослучайных чисел (ГПСЧ, англ. Pseudorandom number generator, PRNG) алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).… … Википедия
Генератор псевдослучайных чисел — (ГПСЧ, англ. Pseudorandom number generator, PRNG) алгоритм, порождающий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному). Современная информатика… … Википедия
Датчик случайных чисел — Генератор псевдослучайных чисел (ГПСЧ, англ. Pseudorandom number generator, PRNG) алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).… … Википедия
Криптостойкий генератор псевдослучайных чисел — Генератор псевдослучайных чисел (ГПСЧ, англ. Pseudorandom number generator, PRNG) алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).… … Википедия
Псевдослучайное число — Генератор псевдослучайных чисел (ГПСЧ, англ. Pseudorandom number generator, PRNG) алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).… … Википедия
Криптографически стойкий генератор псевдослучайных чисел — (англ. Cryptographically secure pseudorandom number generator, CSPRNG) это генератор псевдослучайных чисел с определенными свойствами, позволяющими использовать его в криптографии. Многие прикладные задачи криптографии требуют случайных… … Википедия
Задача о разорении игрока — Задача о разорении игрока задача из области теории вероятностей. Подробно рассматривалась российским математиком А. Н. Ширяевым в монографии «Вероятность»[1] … Википедия
Подробно о генераторах случайных и псевдослучайных чисел
Введение
Как отличить случайную последовательность чисел от неслучайной?
Чуть более сложный пример или число Пи
Последовательность цифры в числе Пи считается случайной. Пусть генератор основывается на выводе бит представления числа Пи, начиная с какой-то неизвестной точки. Такой генератор, возможно и пройдет «тест на следующий бит», так как ПИ, видимо, является случайной последовательностью. Однако этот подход не является критографически надежным — если криптоаналитик определит, какой бит числа Пи используется в данный момент, он сможет вычислить и все предшествующие и последующие биты.
Данный пример накладывает ещё одно ограничение на генераторы случайных чисел. Криптоаналитик не должен иметь возможности предсказать работу генератора случайных чисел.
Отличие генератора псевдослучайных чисел (ГПСЧ) от генератора случайных чисел (ГСЧ)
Источники энтропии используются для накопления энтропии с последующим получением из неё начального значения (initial value, seed), необходимого генераторам случайных чисел (ГСЧ) для формирования случайных чисел. ГПСЧ использует единственное начальное значение, откуда и следует его псевдослучайность, а ГСЧ всегда формирует случайное число, имея в начале высококачественную случайную величину, предоставленную различными источниками энтропии.
Энтропия – это мера беспорядка. Информационная энтропия — мера неопределённости или непредсказуемости информации.
Можно сказать, что ГСЧ = ГПСЧ + источник энтропии.
Уязвимости ГПСЧ
Линейный конгруэнтный ГПСЧ (LCPRNG)
Распространённый метод для генерации псевдослучайных чисел, не обладающий криптографической стойкостью. Линейный конгруэнтный метод заключается в вычислении членов линейной рекуррентной последовательности по модулю некоторого натурального числа m, задаваемой следующей формулой:
где a (multiplier), c (addend), m (mask) — некоторые целочисленные коэффициенты. Получаемая последовательность зависит от выбора стартового числа (seed) X0 и при разных его значениях получаются различные последовательности случайных чисел.
Для выбора коэффициентов имеются свойства позволяющие максимизировать длину периода(максимальная длина равна m), то есть момент, с которого генератор зациклится [1].
Пусть генератор выдал несколько случайных чисел X0, X1, X2, X3. Получается система уравнений
Решив эту систему, можно определить коэффициенты a, c, m. Как утверждает википедия [8], эта система имеет решение, но решить самостоятельно или найти решение не получилось. Буду очень признателен за любую помощь в этом направлении.
Предсказание результатов линейно-конгруэнтного метода
Основным алгоритмом предсказания чисел для линейно-конгруэнтного метода является Plumstead’s — алгоритм, реализацию, которого можно найти здесь [4](есть онлайн запуск) и здесь [5]. Описание алгоритма можно найти в [9].
Простая реализация конгруэнтного метода на Java.
Отправив 20 чисел на сайт [4], можно с большой вероятностью получить следующие. Чем больше чисел, тем больше вероятность.
Взлом встроенного генератора случайных чисел в Java
Многие языки программирования, например C(rand), C++(rand) и Java используют LСPRNG. Рассмотрим, как можно провести взлом на примере java.utils.Random. Зайдя в исходный код (jdk1.7) данного класса можно увидеть используемые константы
Метод java.utils.Randon.nextInt() выглядит следующим образом (здесь bits == 32)
Результатом является nextseed сдвинутый вправо на 48-32=16 бит. Данный метод называется truncated-bits, особенно неприятен при black-box, приходится добавлять ещё один цикл в brute-force. Взлом будет происходить методом грубой силы(brute-force).
Пусть мы знаем два подряд сгенерированных числа x1 и x2. Тогда необходимо перебрать 2^16 = 65536 вариантов oldseed и применять к x1 формулу:
до тех пор, пока она не станет равной x2. Код для brute-force может выглядеть так
Вывод данной программы будет примерно таким:
Несложно понять, что мы нашли не самый первый seed, а seed, используемый при генерации второго числа. Для нахождения первоначального seed необходимо провести несколько операций, которые Java использовала для преобразования seed, в обратном порядке.
И теперь в исходном коде заменим
crackingSeed.set(seed);
на
crackingSeed.set(getPreviousSeed(seed));
И всё, мы успешно взломали ГПСЧ в Java.
Взлом ГПСЧ Mersenne twister в PHP
Рассмотрим ещё один не криптостойкий алгоритм генерации псевдослучайных чисел Mersenne Twister. Основные преимущества алгоритма — это скорость генерации и огромный период 2^19937 − 1, На этот раз будем анализировать реализацию алгоритма mt_srand() и mt_rand() в исходном коде php версии 5.4.6.
Можно заметить, что php_mt_reload вызывается при инициализации и после вызова php_mt_rand 624 раза. Начнем взлом с конца, обратим трансформации в конце функции php_mt_rand(). Рассмотрим (s1 ^ (s1 >> 18)). В бинарном представление операция выглядит так:
10110111010111100111111001110010 s1
00000000000000000010110111010111100111111001110010 s1 >> 18
10110111010111100101001110100101 s1 ^ (s1 >> 18)
Видно, что первые 18 бит (выделены жирным) остались без изменений.
Напишем две функции для инвертирования битового сдвига и xor
Тогда код для инвертирования последних строк функции php_mt_rand() будет выглядеть так
Если у нас есть 624 последовательных числа сгенерированных Mersenne Twister, то применив этот алгоритм для этих последовательных чисел, мы получим полное состояние Mersenne Twister, и сможем легко определить каждое последующее значение, запустив php_mt_reload для известного набора значений.
Область для взлома
Если вы думаете, что уже нечего ломать, то Вы глубоко заблуждаетесь. Одним из интересных направлений является генератор случайных чисел Adobe Flash(Action Script 3.0). Его особенностью является закрытость исходного кода и отсутствие задания seed’а. Основной интерес к нему, это использование во многих онлайн-казино и онлайн-покере.
Есть много последовательностей чисел, начиная от курса доллара и заканчивая количеством времени проведенным в пробке каждый день. И найти закономерность в таких данных очень не простая задача.
Задание распределения для генератора псевдослучайных чисел
Для любой случайной величины можно задать распределение. Перенося на пример с картами, можно сделать так, чтобы тузы выпадали чаще, чем девятки. Далее представлены несколько примеров для треугольного распределения и экспоненциального распределения.
Треугольное распределение
Приведем пример генерации случайной величины с треугольным распределением [7] на языке C99.
Экспоненциальное распределение
Тесты ГПСЧ
Некоторые разработчики считают, что если они скроют используемый ими метод генерации или придумают свой, то этого достаточно для защиты. Это очень распространённое заблуждение. Следует помнить, что есть специальные методы и приемы для поиска зависимостей в последовательности чисел.
Одним из известных тестов является тест на следующий бит — тест, служащий для проверки генераторов псевдослучайных чисел на криптостойкость. Тест гласит, что не должно существовать полиномиального алгоритма, который, зная первые k битов случайной последовательности, сможет предсказать k+1 бит с вероятностью большей ½.
В теории криптографии отдельной проблемой является определение того, насколько последовательность чисел или бит, сгенерированных генератором, является случайной. Как правило, для этой цели используются различные статистические тесты, такие как DIEHARD или NIST. Эндрю Яо в 1982 году доказал, что генератор, прошедший «тест на следующий бит», пройдет и любые другие статистические тесты на случайность, выполнимые за полиномиальное время.
В интернете [10] можно пройти тесты DIEHARD и множество других, чтобы определить критостойкость алгоритма.