Как вычислить миллиард факториалов за 60 миллисекунд с помощью SIMD

Цифровое искусство NFT

Вычисление факториала — классическая задача в программировании и математике, которая стала особенно актуальна с ростом требований к скорости и эффективности алгоритмов. Обычно факториалы, особенно больших чисел, вызывают серьезные затруднения из-за экспоненциального роста вычислительной сложности. Представьте задачу: нужно вычислить факториалы миллиарда чисел максимально быстро. Наивное решение здесь абсолютно неприемлемо — такой подход займет часы, если не дни, даже на современном оборудовании. Однако современные методы и архитектуры процессоров, такие как SIMD (Single Instruction Multiple Data), позволяют значительно ускорить вычисления, доводя время обработки до нескольких десятков миллисекунд.

Раскрывая секреты таких достижений, мы рассмотрим подходы, использованные для решения задачи вычисления миллиардов факториалов за рекордные 60 миллисекунд без использования сложных методов вроде преобразования Фурье (FFT) и предварительных вычислений. Основа, с которой стоит начать — классический наивный алгоритм, разделяющий задачу на блоки длиной 2 в степени 16 со последовательным вычислением факториалов. Такой подход, хоть и прост, в реальности демонстрирует время работы около трех с половиной секунд, что слишком долго для современных требований. Чтобы добиться значительного ускорения, применяют математические теоремы, к примеру, теорему Вильсона. Согласно ей, существует фундаментальное соотношение между факториалом числа и факториалом дополнения к простому модулю.

Использование этого факта позволяет сократить вычисления максимум в два раза, ориентируясь на меньшие из двух чисел – n и p-1-n, где p – модуль. Впрочем, даже этот прием не дает значительного результата в масштабах необходимой оптимизации, поэтому следующий шаг — факторизация чётных чисел. В основе factorial лежит произведение всех целых чисел до n, включая чётные и нечётные. Отделяя чётные члены, которые представляют собой возведение двойки в степень, и оставляя произведение только нечётных чисел, можно существенно снизить вычислительную нагрузку. Произведение всех нечётных чисел называется двойным факториалом, и вычислять его зачастую намного эффективнее.

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

Такой подход позволяет еще раз повысить скорость выполнения за счет одновременной работы нескольких конвейеров CPU. Однако настоящим прорывом в оптимизации стало внедрение SIMD. Это технология, позволяющая выполнять одну инструкцию одновременно над несколькими блоками данных. В нашей задаче это означает, что умножения и другие операции над числами можно делать пакетами. Технология подразумевает применение векторизованного умножения по методу Монтгомери, который особенно удобен для работы по модулю, необходимого для вычисления факториала по модулю M = 998244353.

Соблюдение особенностей Монтгомери в векторизованном формате позволяет минимизировать количество операций и эффективно управлять степенями двойки, которые возникают в умножениях. Разумеется, применение SIMD избавляет от необходимости обрабатывать каждое число по отдельности, сокращая время примерно в 2,4 раза по сравнению с инструкционным параллелизмом. Однако при переходе на такие методы появляется новая сложность — увеличение вычислений, связанных с вычислением быстрой степени двойки по модулю и обращениями по модулю. Наивные методы требуют логарифмического времени для этих операций и начинают доминировать над общей производительностью. Чтобы решить проблему, применяют запоминание (кэширование) заранее вычисленных степеней двойки и их повторное использование, что дает переход от логарифмического ко времени, близкому к константному для каждого запроса.

Аналогично, массовое вычисление обратных по модулю производится через цепочку операций, максимально оптимизированную для сокращения времени с O(n log p) до O(n + log p), где n — количество вычисляемых чисел, а p — модуль. Такая оптимизация позволяет снизить время почти на 20%. В результате этих усилий удалось снизить время с нескольких секунд до примерно 100 миллисекунд, что уже впечатляет с точки зрения производительности. Но осталось последнее узкое место: высокое время для небольших значений n из-за особенностей редукции через “нечетный факториал”. Здесь применяется смешанный подход: для больших уровней рекурсии используется оптимизированный вычислитель нечётного факториала, а как только n опускается ниже определённого порога, выполнение переходит к наивному вычислению классического факториала.

Такой гибридный метод позволяет добиться ещё примерно 1,5-кратного ускорения и свернуть итоговое время до рекордных 60 миллисекунд. Итоговый алгоритм демонстрирует, что даже для таких "тяжелых" математических операций, как вычисление миллиардов факториалов, современные технологии и методики позволяют добиваться впечатляющей скорости без использования сложных и ресурсоемких методов. Большая часть успеха достигается не за счет классических оптимизаций сложности, а именно за счет тонкой настройки архитектуры вычислений под аппаратные возможности, таких как SIMD и эффективная организация памяти. Этот опыт особенно полезен для разработчиков и исследователей, работающих с криптографическими алгоритмами, численной математикой и интенсивными вычислениями в реальном времени. В заключение стоит отметить, что дальнейшие улучшения возможны, но они зачастую связаны с довольно сложными манипуляциями и иногда опускаются до уровня микроскопических оптимизаций, превышающих уровень рентабельности.

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