Алгоритмы *

История Фила Катца — это классическая IT-драма: блестящий взлёт, жёсткая конкуренция, суды, огромный успех и, в конечном итоге, личная трагедия.

Как повернуть время вспять и выиграть Assembly с DOS-демкой в 2025-м году.
Разбираем олдскульные эффекты на примере демки "Demoded".

Секреты, хитрости и откровенное жульничество российского демомэйкинга.
История в картинках.

Сразу оговорюсь, что обычно я не занимаюсь компьютерной безопасностью и не интересуюсь, а занимаюсь алгоритмами и структурами данных - в прикладном применении это оптимизация быстродействия, высокопроизводительные вычисления типа CUDA, AVX512, многопоточность, что применяется например для майнеров криптовалют. Так я влез в криптанализ, ибо области, получается, соприкасаются. Был у меня заказ от человека, который хотел очень быстро на видеокартах перемножать 256-битные числа в 512-битные произведения. Я конечно сделал как он хотел, но вот пришла идея: так а зачем перемножать безчисленное количество чисел, если в принципе можно разложить на множители 512-битное число имея текущие технологии? Об этом дальше и речь.

Дано:

Привет! Я Рома, бэкендер-питонист в KTS.

Это вторая статья в моем цикле об алгоритме архивации bzip2. Первую можно прочитать здесь, но для понимания сегодняшней темы она необязательна. Ниже я разберу преобразование Барроуза-Уилера — ключевой этап сжатия bzip2.

Недавно я прочёл книгу «Кому нужна математика?» Нелли Литвак и Андрея Райгородского — и она меня по-настоящему зацепила. Это короткие, живые рассказы о том, как математика помогает решать важные и неожиданные задачи: от составления расписаний до защиты интернет-трафика. В этом посте я перескажу три истории из книги, которые особенно меня удивили

Мне очень нравится знаменитая цитата Ричарда Фейнмана:

«То, что я не могу создать, я не понимаю»

Она кажется мне великолепной, и я считаю, что она справедлива для многих областей знания (если немного творчески подойти к значению слова «создать»). Наверно, этому принципу я обязан за всё, в чём по-настоящему хорош. Кто-то скажет, что стоит стараться не изобретать велосипед, но они ошибаются: нужно изобретать собственный велосипед, потому что так вы узнаете о его устройстве больше, чем после прочтения тысячи книг.

Сегодня, в 2025 году, красота и ремесло написания ПО подвергаются разрушению. ИИ угрожает тем, что заменит нас (или, по крайней мере, заберёт все самые приятные аспекты нашего ремесла), а разработка ПО становится всё более стандартизированной, выверенной, упакованной и индустриализированной. Разработке программного обеспечения нужно больше простых удовольствий. Я выяснил, что создание хобби-программ — отличный способ снова напомнить себе, почему вообще я начал работать с компьютерами.

Недавно меня заинтересовала такая задача: как лучше всего определить, что в строке есть гласная?

Казалось бы, тривиальный вопрос, правда?

Но, начав разбираться, я осознал, что задача гораздо глубже. Я бросил себе вызов: придумать как можно больше способов обнаружения гласной. Я даже попросил присоединиться ко мне нескольких друзей. Какой способ самый быстрый? Каким никогда не стоит пользоваться? Какой самый умный? Какой самый удобочитаемый?

В этом посте я рассмотрю 11 способов обнаружения гласных, алгоритмический анализ, дизассемблирование байт-кода Python, реализацию CPython и даже исследую опкоды скомпилированного регулярного выражения. Поехали!

В 2006 году АНБ скрыла в криптографическом стандарте Dual EC DRBG математический бэкдор. Агентство отрицало его наличие восемь лет. Затем утечки Сноудена подтвердили его существование.

Двойные эллиптические кривые (Dual Elliptic Curve) используются как безопасные генераторы случайных чисел (RNG). Математический бэкдор позволял правительству США расшифровывать SSL-трафик Интернета (Green 2013)¹.

Эта статья будет технически глубоким исследованием для программистов. Мы реализуем и исходную правительственную научную статью (SP 800-90 2006)², и бэкдор, обнаруженный исследователями Microsoft (Shumow & Ferguson 2007)³.

На моём домашнем компьютере для взлома 28 байт (не бит) при помощи этого бэкдора требуется 2 минуты. Представьте, какой объём Интернет-трафика правительство США могло расшифровывать при помощи суперкомпьютеров Министерства обороны.

Резервуарное сэмплирование — это методика выбора справедливого случайного образца, когда неизвестен размер множества, из которого выполняется выборка. К концу этой статьи вы будете знать:

• Когда может потребоваться резервуарное сэмплирование.

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

• Простой способ реализации резервуарного сэмплирования на случай, если вам оно понадобится.

"Попросите Якоби или Гаусса публично высказать своё мнение — не о истинности, а о важности этих теорем. Позже, я надеюсь, найдутся люди, которым будет выгодно разобраться во всём этом хаосе."

Этими словами заканчивалось письмо Эвариста Галуа, написанное для своего друга Огюста Шевалье за два дня до его смерти от полученных на дуэли ран на 21 году жизни. Ни Якоби, ни Гаусс в его теоремах не разобрались, зато спустя 15 лет разобрался Жозеф Лиувилль и опубликовал работы Галуа, ставшие впоследствии фундаментом современной алгебры, известные сейчас как теория Галуа. В статье расскажу про одну из частей этой теории - поля Галуа, получившая настолько повсеместное применение в криптографии и избыточном кодировании, что Intel и AMD выпустили набор процессорных расширений для эффективной реализации операций над этими полями.

Заметка! Если вам довелось использовать/реализовывать поля Галуа, то большая часть статьи для вас скорее всего будет не интересна, но возможно в последних разделах будет что-то для вас новое.

Помните, как долго выполняется сложение на бумаге?

¹¹ ¹
6876
+ 3406
------
10282

Начиная с единиц, мы складываем 6 + 6 = 12, записываем 2 и переносим 1. Затем пошагово двигаемся влево, пока складываемые разряды не закончатся.

При реализации сложения больших чисел (например, от 2⁶⁴ и выше) обычно пишут код, похожий на этот алгоритм. Любопытно здесь то, что существует простой трюк, позволяющий существенно ускорить этот процесс на современных CPU.

Но сначала я задам вопрос: почему сложение столбиком мы начинаем с самого младшего разряда? Почему бы не начать слева?

Дело, разумеется, в переносе. Мы не можем точно знать, каким будет текущий разряд числа, пока не выполним все сложения справа от этого разряда.

Вы знаете, что такое прогрессивный JPEG? Можете почитать хорошее объяснение. Идея заключается в том, что вместо загрузки изображения сверху вниз оно сначала грузится размытым, а потом постепенно становится чётче.

Что, если мы применим тот же принцип к передаче JSON?

Парадокс двух детей Вы встретили на прогулке соседей с сыном. Известно, что у них двое детей. Какова вероятность, что второй — тоже мальчик?

Казалось бы, детская задачка, где нужно просто “вспомнить формулу”, но всё не так однозначно. Если задать этот вопрос прохожему, он, скорее всего, скажет ½. Преподаватель математики, возможно, ответит ⅓. Кто из них прав?

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

Вопреки распространенному мнению, теория вероятностей не говорит, возможна ли та или иная ситуация. Прежде чем что-то считать, придется подготовить фундамент — идеализировать наблюдение, понять, что именно мы считаем случайным и построить модель эксперимента. Без этого никакие формулы не помогут.

Парадоксы, о которых пойдет речь, — не логические ошибки. Это ситуации, в которых само понятие вероятности начинает колебаться. Они не ломают теорию, но обнажают, где она требует особенной осторожности. Именно в таких местах теория вероятностей становится особенно странной — и особенно интересной.

В этой статье — три таких истории. В первой один и тот же факт даёт разные вероятности, если по-разному устроено наблюдение. Во второй один и тот же объект может быть “случайным” множеством способов. А в третьей невозможно придумать, как сделать задачу математически строгой.

По дороге мы обсудим, что такое вероятностная модель, геометрическая вероятность и математическое ожидание. А в конце поговорим о том, почему в теории вероятностей у одной задачи могут быть несколько ответов и как с этим жить. А еще, вас ждет красивая задача — бонус для тех, кто дочитает статью до конца.

А пока — вернёмся к соседям с мальчиком. Разберемся, почему эта задачка не так проста, как кажется на первый взгляд.

Эта статья — краткая заметка о двух связанных друг с другом эмпирических правилах.

Поднимайте If вверх

Если внутри функции есть условие if, то подумайте, нельзя ли его переместить в вызывающую сторону:

// ХОРОШО

fn frobnicate(walrus: Walrus) {

... }

// ПЛОХО

fn frobnicate(walrus: Option<Walrus>) {

let walrus = match walrus {

Some(it) => it,

None => return,

};

...

}

В подобных примерах часто существуют предварительные условия: функция может проверять предусловие внутри и «ничего не делать», если оно не выполняется, или же может передать задачу проверки предварительного условия вызывающей её стороне, а при помощи типов (или assert) принудительно удовлетворить этому условию. Подъём проверок вверх, особенно в случае предварительных условий, может иметь лавинообразный эффект и привести к уменьшению общего количества проверок. Именно поэтому и возникло это правило.

Сложность текста: 2-3/5

Необходимые знания: должно быть достаточно основ теории многочленов, например, формул Виета

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

Интернет переполнен «математическими задачками с эмодзи». Они более-менее продуманы, поэтому в них легко запутаться, и у людей получаются разные ответы, что вызывает споры и обсуждения, делая посты виральными и так далее...

Естественно, настоящим математикам это надоело. В начале 2017 года на Reddit появился пост с заголовком «Меня утомила вся эта фейсбучная фруктовая математика. Хочет кто-нибудь придумать действительно сложную математическую задачу, чтобы побороться с этим явлением?».

Я долгое время занимаюсь построением 3D копий городов в проприетарном игровом движке на основе картографических данных. Суммарно это сложная задача, успех выполнения которой заключется в решении небольшого набора больших проблем. Одной из таких проблем является отрисовка точного ландшафта на основе реальных данных. Далее я постараюсь расказать обо всех R&D этапах и технических особенностях, с которыми пришлось столкнуться, а вконце будет несколько сравнений сгенерированного ландшафта с фотографиями реальных мест.

Показанным ниже кодом вы можете проверить на високосность год в интервале 0 ≤ y ≤ 102499 всего примерно тремя командами CPU:

bool is_leap_year_fast(uint32_t y) {

return ((y * 1073750999) & 3221352463) <= 126976;

}

Как это работает? Ответ на удивление сложен. В статье я объясню процесс; в основном он связан с забавным битовым жонглированием. В конце мы обсудим применение этого кода на практике.

Всё началось невинно. Шёл 2009 год, и я просто хотел портировать Earcut на Flash - для своей мини-игры. Тогда это сработало, но с годами стало понятно: простые решения перестают работать, как только хочешь выжать из них максимум.