Множество Мандельброта. Суперсэмплинг 8x8 (64 прохода) — впервые в мире

Вот так. Впервые в мире. Суперсэмплинг (SSAA) — ресурсоемкий метод сглаживания, увеличивающий число выборок на пиксель для повышения качества изображения. При значении 8x (N=8) сцена рендерится в разрешении, в 8 раз превышающем целевое, по обеим осям, создавая 64 (или 8 х 8) выборки на пиксель. Изображение просчитывается в более высоком разрешении, а затем принудительно уменьшается до разрешения дисплея, устраняя лесенки и улучшая чёткость. Это очень высокая нагрузка! Это не 1920 на 1920 пикселя а в 8x8 больше - 15360 на 15360 пикселя! Такое никто, кроме меня, делает в мире. Для множество Мандельброта.

https://habr.com/ru/articles/1010052/

Алгоритмы и Структуры данных

Две скрученные фигуры разрешают многовековую топологическую загадку

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

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

Ответ — да. Измеряя определённые расстояния и углы на поверхности Земли, мы можем определить, что Земля — это сфера, а не, скажем, плоская или кольцеобразная фигура, — даже без спутникового снимка.

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

https://habr.com/ru/companies/first/articles/1010700/

Алгоритмы и Структуры данных

Множество Мандельброта. Суперсэмплинг 2x2 (4 прохода). DwmFlush — синхронизация с монитором 60 fps

Множество Мандельброта. 80-бит FPU x87. OpenMP - параллельным программированием на уровне многопоточности. Синий, зеленый и красный - синусоидальными и косинусоидальными волнами: 127 + 127 cos(2 PI a / 255) и 127 + 127 sin(2 PI a / 255). DwmFlush - синхронизация с монитором 60 fps. Суперсэмплинг 2x2 (4 прохода). Делал я. Посмотрите - движется! Я сделал на g++. Свободно распространяемого компилятора языка C++. Скачайте и посмотрите! Это экзешник, в ГитХаб.

https://habr.com/ru/articles/1011430/

Алгоритмы и Структуры данных

Как я ускорил Python-скрипт в 42 раза, убрав один незаметный цикл

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

Недавно я столкнулся именно с такой ситуацией. Нужно было обработать большой лог-файл — около 8 ГБ — и извлечь из него статистику по пользователям. Скрипт работал почти 9 минут, хотя логика казалась предельно простой.

https://habr.com/ru/articles/1011582/

Алгоритмы и Структуры данных

Lattelua — когда Lua уже мало

Если вы хоть раз встраивали Lua в свой проект — будь то игровой движок, высоконагруженный веб-сервер на OpenResty или конфигуратор сложного сетевого оборудования — вы знаете, за что мы его любим:)
А любим мы его — за компактность, быстроту, встраиваемость и предсказуемость. Не любим — за аскетичный синтаксис, отсутствие привычных конструкций и постоянное «изобретение велосипеда».

Эта статья — обзор диалекта Lattelua: зачем он нужен, чем отличается от других диалектов, и почему его особенно удобно использовать в уже существующих проектах, где Lua — встраиваемый язык.

https://habr.com/ru/articles/1011614/

Алгоритмы и Структуры данных

Сложные вычисления — в минимальном объёме памяти

По закону Мура плотность транзисторов на микросхеме удваивается каждые 24 месяца. Производительность CPU, GPU, TPU и NPU растёт уже несколько десятилетий, что привело нас вплотную к задачам эмуляции мозга и Сверхинтеллекта.

https://habr.com/ru/companies/ruvds/articles/1011548/

Алгоритмы и Структуры данных

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

Мы привыкли думать о вычислениях как о битах, регистрах и арифметике. А что, если базовой единицей вычисления сделать не бит, а локальную геометрическую конфигурацию тетраэдров? В этой статье я покажу дискретный тетраэдрический движок состояний, симметрийную канонизацию, аттракторы, иерархические jump-таблицы и реальные замеры на RTX 3090 — с измеренным exact-ускорением в 554.92 раза на одной и той же задаче.

https://habr.com/ru/articles/1011646/

Алгоритмы и Структуры данных

Последний экзамен человечества: насколько «умен» ИИ?

Отличительной особенностью научного подхода является отсутствие веры на слово. Любое утверждение не может считаться фактом, пока не будет установлена его истинность. А для этого необходимо задать множество вопросов, провести множество измерений, тестов, моделирований и т. д. Все, что есть во Вселенной, осязаемое или нет, может быть в той или иной степени измерено. Не исключением являются знания, которые проверяются как в школах, так и в университетах с помощью специально составленных экзаменов. С появлением генеративных ИИ не утихаю дебаты об уровне их знаний и достоверности той информации, которую они выдают на запрос. Те тесты, которые ранее считались показательными, более не могут полноценно оценить ИИ. По этой причине ученые из Техасского университета A&M (Колледж-Стейшен, Техас, США) разработали «Последний экзамен человечества» - всеобъемлющий текст знаний по различным направлениям для ИИ. Из каких вопросов состоял тест, и как себя показали самые популярные генеративные ИИ? Ответы на эти вопросы мы найдем в докладе ученых.

https://habr.com/ru/companies/ua-hosting/articles/1011190/

Алгоритмы и Структуры данных

Нескучное программирование. Обобщения (ч.2)

Это не отдельная статья, а продолжение статьи про теорию объектов в с++, почему объекты в плюсах такие какие есть. Все завершенные главы я также выкладываю на github'e в английском и русском варианте. Продолжаем разбираться в теории С++...

Отдельного разговора заслуживает идентичность объектов, потому что в реальном мире конкретные сущности обладают идентичностью и Сократ останется Сократом независимо от того, перекрасил ли он волосы, сменил адрес или умер, а государство остаётся тем же государством, даже если меняет флаг, конституцию или размер населения.

https://habr.com/ru/articles/1011012/

Алгоритмы и Структуры данных

Почему Python + Numba обгоняет C? Эксперимент с алгоритмом прогонки

Все знают: если нужно быстро считать – пиши на C. Python – для прототипов, но в продакшене он тормозит. Однако с появлением NumPy и JIT-компиляторов (Numba) границы стираются. Более того, в некоторых случаях Python может даже обогнать наивную реализацию на C.

https://habr.com/ru/articles/1012122/

Алгоритмы и Структуры данных

Умножение матриц: пример использования расширения ARM SME2 в Apple M4 Pro

В конце 2020 года я купил MacBook Pro 13 на процессоре Apple M1, очень хотелось испытать процессоры на архитектуре ARM. Почти сразу на чипе Apple M1 был найден вычислительный блок для матричных операций Apple AMX. Для Apple AMX не было документации, он не использовался в Apple Accelerate, но несколько энтузиастов занимались реверс-инжинирингом и анализом производительности ("https://github.com/corsix/amx").

В 2024 году вышли компьютеры на базе семейства процессоров Apple M4, у которых блок AMX задействован для выполнения инструкций из Scalable Matrix Extension 2 (сайт ARM недоступен в РФ) (ARM SME2).

В статье рассмотрим использование расширения ARM SME2 на примере умножения заполненных матриц. Увидим, как выжать максимум из процессора и получить прирост производительности в десятки раз.

https://habr.com/ru/articles/1012528/

Алгоритмы и Структуры данных

Бродим по лабиринту

Оптимизация поиска выхода из лабиринта представляется относительно простой задачей. Но она подразумевает накопление данных, обучение, если угодно.
Как только возникает потребность накапливать данные, стоит исходить из того, что этих данных станет много и придётся прибегнуть к технологиям из области баз данных.
Здесь представлена робкая попытка разобраться в теме.

https://habr.com/ru/articles/1013192/

Алгоритмы и Структуры данных

Как определить выпуклость многоугольника на C: от геометрии к коду

Зачем вообще определять, выпуклый ли многоугольник?

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

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

https://habr.com/ru/articles/1013262/

Алгоритмы и Структуры данных

Процессор в вашем компьютере угадывает будущее. И ошибается в 5% случаев

В прошлую пятницу я объяснял джуну, почему его код на отсортированном массиве работает в шесть раз быстрее, чем на неотсортированном. Тот же массив, тот же алгоритм, и те же данные. Просто в другом порядке. Джун смотрел на меня как на сумасшедшего и, честно говоря, я его понимаю.

Потому что ответ звучит безумно: процессор внутри вашего ноутбука постоянно пытается предсказать будущее. Буквально. Он гадает, какая ветка if выполнится ещё до того, как условие будет вычислено. И на отсортированных данных ему угадывать проще.

Ну, давайте разбираться.

https://habr.com/ru/articles/1013098/

Алгоритмы и Структуры данных

Клод Шеннон. Отец цифровой эры

В истории науки и техники есть имена, которые ассоциируются с конкретными изобретениями: Эдисон и лампочка, Белл и телефон, Попов и радио. Но есть и другая категория гениев, чьи имена стоят за целыми мирами, за фундаментом, на котором возведено здание современной цивилизации. Клод Элвуд Шеннон — именно такой человек. Его имя не на слуху у широкой публики, но без его прозорливости наш мир был бы совсем иным: не было бы ни Интернета в его нынешнем виде, ни мобильной связи, ни компакт-дисков, ни даже привычной нам работы компьютеров. Он не просто изобрёл очередное устройство; он создал универсальный язык и математический аппарат для понимания самой сути информации, превратив её из абстрактного понятия в измеримую величину.

https://habr.com/ru/companies/timeweb/articles/1013586/

Алгоритмы и Структуры данных

Как мы пришили LLM «спинной мозг»: архитектура рефлексов для ИИ-агентов в 60 FPS

Интеграция современных LLM в геймдев, виртуальных ассистентов и робототехнику сейчас напоминает попытку прикрутить двигатель от космического шаттла к телеге. У вас есть невероятно умная модель, которая понимает тончайший контекст, но её inference latency (задержка вывода) убивает любой пользовательский опыт.

Пока ваш ИИ-NPC парсит входящий аудиопоток, отправляет запрос по API, ждет генерации ответа и распаковывает JSON в анимацию, проходит от 1 до 3 секунд. В динамичной среде — это вечность.

Недавно мы выкатили визуальный прототип нашего движка на одной развлекательной площадке. В ответ мы получили классическое: "Рано демонстрировать 'честные 60 FPS'. У вас там просто калейдоскоп беспорядочных кадров, мыло и кривые пальцы".

Ребята смотрели на дебаг-вывод и оценивали "обертку", совершенно не заметив "мотор". Визуализация была лишь сырым тестом инференса. В этой статье я расскажу, как мы построили Dual-Process Architecture (Система 1 + Система 2), которая позволяет ИИ реагировать на события за миллисекунды, менять личность на лету и обучаться в реальном времени.

https://habr.com/ru/articles/1013726/

Алгоритмы и Структуры данных

Конец эпохи вероятностного ИИ: почему гонка за GPU от Nvidia — это архитектурный тупик

Индустрия генеративного искусственного интеллекта больна. Симптомы этой болезни видны невооруженным глазом: шесть пальцев на руках, нарушенная геометрия объектов в движении и рассинхрон звука с артикуляцией (AV-desync). Но вместо того, чтобы лечить причину математикой, техногиганты пытаются заглушить боль грубой силой, заливая проблему деньгами и сжигая мегаватты энергии на кластерах Nvidia H100.

Сегодня мы наблюдаем классическую архитектурную ошибку: попытку решить фундаментальный математический изъян экстенсивным наращиванием "железа". И эта гонка приведет к неизбежному краху текущей бизнес-модели монополистов.

https://habr.com/ru/articles/1014130/

Алгоритмы и Структуры данных

В каждом JPEG зашита модель вашей сетчатки. Буквально

После того как я написал статью про то, что ваш монитор не умеет показывать бирюзовый и 65% видимых цветов для него просто не существуют, один мой знакомый (далекий правда от технической отрасли) спросил: «Окей, монитор врёт, а что тогда делает JPEG с оставшимися 35%?» И это хороший вопрос. Я полез в спеку, а через полчаса забыл, зачем вообще полез. Потому меня уже интересовало другое: ребята, которые в 1992-м финализировали этот стандарт, по сути заревёрсили человеческое зрение и запихнули его в алгоритм сжатия.

И не метафорически. В прошлой статье я рассказал (и показал), как монитор эксплуатирует метамерию — три огонька вместо полного спектра, и мозг не замечает подмены. Так вот, JPEG идёт дальше. Здесь каждый этап пайплайна — это конкретный хак, эксплуатирующий конкретный баг в вашей зрительной системе. Монитор обманывает колбочки, а JPEG обманывает всё остальное, от контрастной чувствительности до того, как кора мозга собирает картинку из частот.

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

https://habr.com/ru/articles/1013668/

Алгоритмы и Структуры данных

Строим перспективу по изображению

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

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

https://habr.com/ru/articles/1014374/

Алгоритмы и Структуры данных

TurboQuant. Новый алгоритм сжатия от Google

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

Думаю, будет правильно первым делом дать ссылку на оригинальную публикацию от самих Google с подробным описанием алгоритма:

https://research.google/blog/turboquant-redefining-ai-efficiency-with-extreme-compression

https://habr.com/ru/articles/1015092/

Алгоритмы и Структуры данных