В библиотеках различных языков программирования часто может быть включена функция для вычисления гипотенузы прямоугольного треугольника (или вы сами можете написать такую функцию для решения той или иной задачи).
На первый взгляд это может показаться тривиальной задачей, не так ли? Если сторонами треугольника являются x и y, то, формально, формулой для вычисления гипотенузы будет:
sqrt(x*x + y*y)
Это работает теоретически, но на практике данный подход может приводить к ошибке. Если значение x достаточно велико, то вычисление x*x может привести к переполнению типа данных (ни один тип данных от этого не застрахован, если не рассматривать длинную арифметику), и результатом вычислений будет бесконечность.
Одним из вариантов избежать вероятности переполнения является следующая последовательность действий:
max = maximum(|x|, |y|);
min = minimum(|x|, |y|);
r = min / max;
return max*sqrt(1 + r*r);
Заметим, что значение подкоренного выражение лежит на интервале от 1 до 2, что никак не может привести к переполнению при вычислении квадратного корня. Единственное место в котором может случиться переполнение, это финальное умножение. Но, если переполнение и произошло, это лишь означает, что результат настолько велик, что не может быть вмещён в используемый тип данных, и это уже не проблема выбора алгоритма а проблема выбора типа данных.
Для того, чтобы увидеть как вышеприведённый алгоритм может преуспеть в то время как решение в лоб упасть, приведём небольшой пример. Пусть M — наибольшее число, которое может быть представлено выбранным типом данных. Для типа данных double, M будет порядка 10308. Пусть x и y эквивалентны величине 0.5 M. Алгоритм должен вернуть значение примерно равное 0.707 M, что не должно переполнить выбранный тип данных. Но решение в лоб не даст правильного ответа, в то время как предложенный алгоритм преуспеет.
Ради интереса проверил стандартную функцию (hypot или _hypot) включённую в math.h, и результат порадовал.
Вывод, который я сделал для себя: если в библиотеку включена какая-то функция, которая на первый взгляд кажется элементарной и пишется в две строчки, то есть большая вероятность, что сделано это не просто так и есть какие-то глубокие причины для такого решения.
По ссылке на оригинальный материал могут быть найдены комментарии к вопросу о том, не будет ли потеряна точность при таком способе нахождения гипотенузы.
Автор: aamuvirkku
