Полный текст
От итераций к формулам: как Clang меняет сложность алгоритмаКомпиляторы часто демонстрируют неочевидные трюки, превращая линейный код в математическую модель. Простая функция суммирования чисел до заданного значения в GCC превращается в оптимизированный цикл с векторизацией. Однако Clang идёт ещё дальше: он распознаёт алгоритм и заменяет его аналитическим решением.Вместо итераций применяются инструкции imul и shr, что меняет сложность вычислений с $O(n)$ на $O(1)$. Подобная трансформация кода доказывает мощь современных оптимизаторов, способных выводить индуктивные переменные в обход явных циклов. Исследуем ассемблерный вывод и разберём математику преобразований.