Как стать автором
Обновить

Скирмионы помогут генерировать настоящие случайные числа

Блог компании Cloud4Y Алгоритмы *Математика *Научно-популярное Физика

По-настоящему случайные числа требуются для нужд кибербезопасности, в играх, для научного моделирования и т. д. Казалось бы, в чём проблема – получить случайное число? Компьютеры легко справляются с этой задачей. Однако на деле большинство случайных чисел, выдаваемых ими, не являются по-настоящему случайными. 

Группа физиков из Университета Брауна разработала метод, который потенциально может генерировать миллионы случайных чисел в секунду. В нём используется поведение скирмионов — крошечных магнитных аномалий, возникающих в некоторых двумерных материалах.

Читать далее
Всего голосов 15: ↑15 и ↓0 +15
Просмотры 1.7K
Комментарии 0

Рандомизированные деревья поиска

Алгоритмы *
Tutorial

Не знаю, как вы, уважаемый читатель, а я всегда поражался контрасту между изяществом базовой идеи, заложенной в концепцию двоичных деревьев поиска, и сложностью реализации сбалансированных двоичных деревьев поиска (красно-черные деревья, АВЛ-деревья, декартовы деревья). Недавно, перелистывая в очередной раз Седжвика [1], нашел описание рандомизированных деревьев поиска (нашлась и оригинальная работа [2]) — настолько простое, что занимает оно всего треть страницы (вставка узлов, еще страница — удаление узлов). Кроме того, при ближайшем рассмотрении обнаружился дополнительный бонус в виде очень красивой реализации операции удаления узлов из дерева поиска. Далее вы найдете описание (с цветными картинками) рандомизированных деревьев поиска, реализация на С++, а также результаты небольшого авторского исследования сбалансированности описываемых деревьев.
Читать дальше →
Всего голосов 88: ↑85 и ↓3 +82
Просмотры 48K
Комментарии 18

Почему я не лезу в криптографию

Криптография *
Перевод
Предлагаю вашему вниманию вольный перевод интересной заметки о тяжком бремени программистов, занимающихся криптографическими алгоритмами. Заметка — личный взгляд человека, который уважает таких программистов, но сам ни за что бы не полез в криптографию.
И вот почему
Всего голосов 101: ↑91 и ↓10 +81
Просмотры 57K
Комментарии 93

Нюансы создания аркады

Разработка игр *Разработка под Android *Unity *
Из песочницы


И вот моя первая попытка выбраться на просторы Хабрахабр.

Недавно в свет вышла моя игра Evasion. Простая аркада, в которой нужно уклоняться от препятствия. Игра сама по себе легка в разработке, но в каждой простоте есть свои подводные камни. О парочке из них я и хочу поговорить в данной статье.
Читать дальше →
Всего голосов 10: ↑7 и ↓3 +4
Просмотры 8.2K
Комментарии 0

Избавляем игрока от раздражения: правильное использование случайных чисел

Разработка игр *
Перевод
image

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

Но есть способ и получше. Используя случайных чисел и их генерирование иным образом, мы можем создавать захватывающий игровой процесс, создающий «идеальный» уровень сложности, не выбешивая при этом игроков. Но прежде чем мы перейдём к этому, давайте рассмотрим основы генераторов случайных чисел (или RNG).
Читать дальше →
Всего голосов 30: ↑27 и ↓3 +24
Просмотры 18K
Комментарии 18

Эффективная генерация числа в заданном интервале

Программирование *Совершенный код *Алгоритмы *Математика *
Перевод
image

В подавляющем большинстве моих постов о генерации случайных чисел рассматривались в основном свойства различных схем генерации. Это может оказаться неожиданным, но производительность алгоритма рандомизации может зависеть не от выбранной схемы генерации, а от других факторов. В этом посте (на который меня вдохновила превосходная статья Дэниела Лемира) мы исследуем основные причины снижения производительности генерации случайных чисел, которые часто перевешивают производительность движка ГПСЧ.

Представьте такую ситуацию:

В качестве домашнего задания Хуан и Саша реализуют одинаковый рандомизированный алгоритм на C++, который будет выполняться на одном университетском компьютере и с одним набором данных. Их код почти идентичен и отличается только в генерации случайных чисел. Хуан торопится на свои занятия по музыке, поэтому просто выбрал вихрь Мерсенна. Саша, с другой стороны, потратил несколько лишних часов на исследования. Саша провёл бенчмарки нескольких самых быстрых ГПСЧ, о которых недавно узнал из соцсетей, и выбрал наиболее быстрый. При встрече Саше не терпелось похвастаться, и он спросил Хуана: «Какой ГПСЧ ты использовал?»

«Лично я просто взял вихрь Мерсенна — он встроен в язык и вроде неплохо работает».

«Ха!», — ответил Саша. «Я использовал jsf32. Он намного быстрее, чем старый и медленный вихрь Мерсенна! Моя программа выполняется за 3 минуты 15 секунд!».

«Хм, неплохо, а моя справляется меньше, чем за минуту», — говорит Хуан и пожимает плечами. «Ну ладно, мне пора на концерт. Пойдёшь со мной?»

«Нет», — отвечает Саша. «Мне… эээ… нужно снова взглянуть на свой код».

Эта неловкая вымышленная ситуация не особо и вымышлена; она основана на реальных результатах. Если ваш рандомизированный алгоритм выполняется не так быстро, как хотелось бы, и узким местом похоже является генерация случайных чисел, то, как это ни странно, проблема может быть и не в генераторе случайных чисел!
Читать дальше →
Всего голосов 31: ↑31 и ↓0 +31
Просмотры 25K
Комментарии 10

История алгоритмов рандомизации «Тетриса»

Разработка игр *Реверс-инжиниринг *Дизайн игр *Игры и игровые консоли
Перевод
image
В 1985 году Алексей Пажитнов и Вадим Герасимов выпустили в свет Tetris. Эта увлекательная и вызывающая сильное привыкание игра требовала от игроков соединять фигуры, появлявшиеся в случайном порядке. С того времени было выпущено более 150 лицензионных версий «Тетриса». Отличаясь игровыми режимами, правилами и реализацией, все они игрались слегка (или очень) по-разному. Рандомизатор «Тетриса» — это функция, возвращающая случайно выбранную фигуру. На протяжении многих лет правила выбора фигур эволюционировали, оказывая влияние на геймплей и саму случайность. Некоторые из этих алгоритмов были подвергнуты реверс-инжинирингу и задокументированы. Я составил список рандомизаторов, которые считаю важными, и покажу в статье, как с годами менялось внутреннее устройство «Тетриса».
Читать дальше →
Всего голосов 75: ↑74 и ↓1 +73
Просмотры 21K
Комментарии 32

Математики на примере «пятнашек» вычисляют, как возникает случайность

Математика *Научно-популярное
Перевод
image

Задача головоломки «пятнашки» — упорядочить пронумерованные плитки. Сегодня математики решили обратную задачу — как перепутать головоломку.

Вероятно, вы играли в «пятнашки». Это расстраивающая, но аддиктивная игра, состоящая из 15 плиток и одного пустого пространства, выстроенных в сетку 4 на 4. Задача заключается в перемещении плиток и выстраивании их в порядке возрастания чисел или, в некоторых версиях, сборке из них изображения.

После своего появления в 1870-х годов она вошла в стандартный набор игр. Кроме того, она привлекла внимание математиков, которые больше века изучали решения головоломок различного размера и начальных конфигураций.

Сегодня появилось новое доказательство решения «игры в 15», но в обратном порядке. Математики Юн Чу и Роберт Хоу из Университета Стони Брук определили количество ходов, необходимое для превращения упорядоченного поля в случайное.
Читать дальше →
Всего голосов 16: ↑15 и ↓1 +14
Просмотры 4.3K
Комментарии 10

Всё, что вы хотели знать о МАС адресе

Сетевые технологии *Беспроводные технологии *Сетевое оборудование

Всем известно, что это шесть байт, обычно отображаемых в шестнадцатеричном формате, присвоены сетевой карте на заводе, и на первый взгляд случайны. Некоторые знают, что первые три байта адреса – это идентификатор производителя, а остальные три байта им назначаются. Известно также, что можно поставить себе произвольный адрес. Многие слышали и про "рандомные адреса" в Wi-Fi.


Разберемся, что это такое.


МАС адрес (media access control address) – уникальный идентификатор, назначенный сетевому адаптеру, применяется в сетях стандартов IEEE 802, в основном Ethernet, Wi-Fi и Bluetooth. Официально он называется «идентификатором типа EUI-48». Из названия очевидно, что адрес имеет длину в 48 бит, т.е. 6 байт. Общепринятого стандарта на написание адреса нет (в противоположность IPv4 адресу, где октеты всегда разделяют точками).Обычно он записывается как шесть шестнадцатеричных чисел, разделенных двоеточием: 00:AB:CD:EF:11:22, хотя некоторые производители оборудования предпочитают запись вида 00-AB-CD-EF-11-22 и даже 00ab.cdef.1122.

Читать дальше →
Всего голосов 111: ↑110 и ↓1 +109
Просмотры 137K
Комментарии 73