Алгоритмы *

В конце 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 на примере умножения заполненных матриц. Увидим, как выжать максимум из процессора и получить прирост производительности в десятки раз.

Все знают, что C быстрее Python. Но мы провели эксперимент с алгоритмом прогонки и обнаружили, что Numba (JIT-компилятор для Python) обгоняет наивный C на 20–25%. Разбираемся, почему так происходит, и сравниваем точность float32/float64.

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

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

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

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

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

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

У вычислительной программы есть два ресурса: время (циклы CPU) и пространство (оперативная память). Но как они заменяют друг от друга? Правда ли задачу, которая решается в полиномиальном пространстве , можно решить за полиномиальное время ?

Как выяснилось, «конвертация сложности» между временем и пространством работает гораздо лучше, чем предполагалось ранее. Новые открытия математиков доказывают, что память можно использовать потрясающе эффективно.

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

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

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

Множество Мандельброта. 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++. Скачайте и посмотрите! Это экзешник, в ГитХаб.

github: Download Latest Version Windows And Source code

Самое полезное - это увеличиваем / уменьшаем и центрируем. Вы на экран любое из множество Мандельброта. Какое вам нравится? Какое интересное? Вы можете все! И потом запишется в файл Mandelbrot.txt - три строки из файла. Вещественная часть центра и мнимая часть центра и ширина видимой области. Потом другая программа читает Mandelbrot.txt и создает Mandelbrot.bmp и уже не суперсэмплинг 2x2 (4 прохода) а 8x8 (64 прохода)!

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

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

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

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

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

Никто не мог найти замкнутую поверхность, нарушающую это правило. Постепенно математикам стало казаться, что таких поверхностей просто не существует. Они ошибались.

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

Это маленькая утилита из командной строке. Которая либо читает Mandelbrot.txt три строки из файла - клавиша 7. И создает Mandelbrot.bmp
Либо клавиша 1-6 - это одно из шести разных мест множество Мандельброта и создает Mandelbrot.bmp
Скачайте и посмотрите. Это экзешник, в ГитХаб
Скачать последнюю версию (Windows и Linux)

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

Правда и то, что со стороны других людей (не наших многомиллионных героев) ситуация может выглядеть по‑другому. 

Представьте детский сад. Один ребёнок приносит коробку конфет. Он её открывает. Показывает всем. Но делиться не собирается.

У остальных детей возникает понятная смесь эмоций: любопытство, раздражение.

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

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

OpenAI выкатила GPT‑5.4 Pro. И если раньше слово “Pro” в названии часто означало просто “чуть больше токенов и подороже”, то теперь это действительно профессорский уровень. Модель берёт сложнейший тест ARC-AGI-2 с результатом 83,3% (против 54% у предшественницы), решает задачи из FrontierMath, которые ещё недавно казались крепостью для ИИ, и... случайно находит в интернете забытую научную статью 2011 года, чтобы срезать путь к ответу.

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

Пристегнитесь, будет интересно!

В 1957 году писатель-фантаст Роберт Хайнлайн так представлял себе людей XXI века: «Делала перерасчет прочности гидропонических оранжерей, но выходило с ошибками. Дважды забывала логарифмы, так что пришлось лезть в таблицу».

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

Зато, чтобы обрести эту сверхспособность, не требуются укусы радиоактивных пауков — достаточно просто прочитать эту статью, а уж пригодится ли в жизни — решайте сами. Может быть в нужный момент калькулятора под рукой не окажется, а может быть просто захочется произвести впечатление на коллег небрежно брошенной фразой: «Корень седьмой степени из пяти это примерно 1,25». Хотите научится быстро считать? Тогда добро пожаловать под кат!

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

Вчера я 4 минуты стоял в подъезде и смотрел, как два лифта одновременно поехали вверх. Все два. На табло — 12, 15, 18. Я на первом. Мне на шестой. И я подумал: вот я кучу лет пишу софт, оптимизирую запросы к базе данных, кеширую всё что движется — а эти две коробки на тросах не могут разобраться, кто из них должен спуститься за мной.

Потом я погрузился в тему. И выяснил, что они не «не могут разобраться». Они математически не способны найти идеальное решение. Вообще никто не способен. Задача диспетчеризации группы лифтов — NP-трудная. То есть буквально: не существует алгоритма, который гарантированно найдёт оптимальный маршрут за разумное время.

И вот уже 60 лет лучшие инженеры мира решают эту задачу эвристиками. По сути — догадками.

Я делаю Beetroot — клипборд-менеджер для Windows на стеке Tauri + React + Rust + SQLite. В моей ежедневной базе 1000+ записей: куски кода, URL-ы, стектрейсы, SQL-запросы, переписки из мессенджеров. Поиск по всему этому должен работать мгновенно и попадать точно в цель.

Сначала я пошёл по простому пути: подключил популярную библиотеку Fuse.js и думал, что задача решена. Но реальные данные буфера обмена оказались для неё патологическим кейсом.

Эта статья — про путь от «просто подключи готовую либу» до самописного 5-уровневого движка с мерж-скорингом. Два дня, 8 итераций, пара красивых продуктовых багов по дороге.

Когда я пишу эту статью, то чувствую себя довольно глупо. На самом деле, это история с моралью «Прежде, чем действовать, изучи вопрос и понимай, в чём заключается твоя цель, потому что иначе потеряешь много времени».

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

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

Данная статья посвящена основе основ нейронауки — линейной алгебре. Если вы когда-либо планируйте изучать искусственные нейронные сети (и не только), то вам необходимо начать именно с этого. Причем не важно, собираетесь ли вы заниматься фундаментальными исследованиями (Data Science) или просто лепить модели в продакшн на конвейере (ML Engineering), вы обязаны знать их математику хотя бы поверхностно. Любые настройки, дообучение и применение даже готовой модели, требуют понимания основ. А по сему данное знание, как минимум, не будет избыточным.

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

В этой статье:
* Понятие вектора;
* Векторизация данных;
* Умножение на скаляр;
* Сложение векторов;
* Норма вектора;
* Скалярное умножение;
* Векторное умножение;
* Практика с кодом;
* Домашняя работа.

Все будет объяснено на красочных примерах в игровой форме. Ничего сложного. А в конце вас ждет самостоятельная практика с кодом.

Приятного чтения!

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

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

Все модели, которые я буду использовать и описывать, выполнены на языке Matlab – среде, изначально созданной для работы с матрицами. Гарантированно они будут работать на версии R2016b и выше.