Дмитpий Hecтepук

Блог о программировании — C#, F#, C++, архитектура, и многое другое

Оптимизация математических выражений

leave a comment »

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

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

Умножение

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

Например, если изначально у нас есть формула

\displaystyle y=ax^2+bx+c

То в целях повышения производительности, мы можем переписать эту формулу как

\displaystyle y=x(ax+b)+c

В первой формуле – 3 умножения и 2 сложения. Во втором – 2 умножения и 2 сложения. Так или иначе мы сэкономили стоимость одного умножения, т.е. срезали как минимум 20% стоимости этого вычисления.

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

  • a^2-b^2=(a+b)(a-b) имеет смысл при условии что умножение дороже сложения.

  • x^2+10x+16=(x+8)(x+2) содержит одно умножение вместо 3-х (!) но подразумевает решение уравнения. Такую оптимизацию очень сложно обобщить, и в общем случае она подразумевает решение практически бесконечного количества уравнений.

Возведение в степень

Функции возведения в степень обычно заточены под нецелые степени, т.е. степень это значение типа float или double и соответственно для вычисления используются ряды Тейлора. Это значит что цена вычисления x^2 в десятки (!) раз больше чем цена x \cdot x.

В долгосрочной перспективе, любое вычисление x^n где n \ge 2, n \in \mathbb{Z} подразумевает \left\lceil \log_{2}n\right\rceil умножений. В принципе, некоторые языки (например С++) имеют перегрузки метода возведения в степень, где параметр степени – целое число (т.е. int). В этом случае никаких дополнительных усилий не требуется. Если же такой функции не существует (например, в .NET), то есть два варианта:

  • Для n=2,3 имеет смысл просто заменить возведение в степень на умножение, т.к. это эффективней и понятнее чем использование сторонней функции.

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

Конечно, существует и просто неэффективное использование функции возведения в степень: например, не имеет смысла считать x^{0.5} когда вместо этого можно намного быстрее посчитать \sqrt{x}. Ну и не будем забывать про совсем уж специализированные оптимизации расчета функций, например всем известный механизм расчета 1/\sqrt{x} Джона Кармака.

Деление

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

\displaystyle \frac{a}{x}+\frac{b}{x}=\frac{a+b}{x}

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

\displaystyle \frac{a}{b}+\frac{c}{d}=\frac{ad+bc}{bd}

Два деления вместо одного имеют смысл, особенно когда деление в 6 раз медленнее умножения.

Введение временных переменных

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

\displaystyle ax^6+bx^3=x^3(ax^3+b)

мы продолжаем считать x^3 дважды, что влечет за собой 4 умножения вместо 2-х. Гораздо проще внедрить временную переменную y=x^3 и потом просто посчитать y(ay+b).

Заключение

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

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

\displaystyle x/4=x\gg 2

Так что оптимизируйте с удовольствием, или используйте программы, которые оптимизируют за вас. ■

Реклама

Written by Dmitri

4 декабря 2012 в 21:42

Опубликовано в Mathematics

Оставить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: