На первый взгляд это может показаться тривиальной задачей, не так ли? Если сторонами треугольника являются 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, и результат порадовал.
Вывод, который я сделал для себя: если в библиотеку включена какая-то функция, которая на первый взгляд кажется элементарной и пишется в две строчки, то есть большая вероятность, что сделано это не просто так и есть какие-то глубокие причины для такого решения.
По ссылке на оригинальный материал могут быть найдены комментарии к вопросу о том, не будет ли потеряна точность при таком способе нахождения гипотенузы.
ссылка на оригинал статьи http://habrahabr.ru/post/165061/
Добавить комментарий