Важность оптимизации алгоритмов

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

R = sqrt((x1-x2)^2 + (y1-y2)^2 + (z1-z2)^2)

Казалось бы, что тут сложного? Но, когда сопроцессор выполняет действие (x1-x2) при примерно равных значениях обоих операндов, происходит потеря большого числа разрядов мантиссы. Чтобы избежать этого, я использую развернутую формулу квадратов и соединение примерно равных величин:

dx^2 = x1^2 – 2*x1*x2 + x2^2

Подкоренное выражение можно заменить на

R^2 = x1^2 + x2^2 + y1^2 + y2^2 + z1^2 + z2^2 –

2 * (x1 * x2 + y1*y2 + z1*z2)

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

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