Программирование
Как найти квадратный корень из числа.
Три простых способа аппроксимации квадратного корня.
Мысль о вычислении квадратного корня может вызвать кошмары из нашей школьной жизни. Больше не надо. С программированием и помощью некоторых замечательных математиков и Википедии поиск квадратного корня будет легкой прогулкой или, самое большее, легким бинарным поиском.
Давайте рассмотрим три разных способа сделать это.
Метод Ньютона-Рафсона.
Этот метод использует линейную аппроксимацию для нахождения квадратного корня из целого числа. Метод Ньютона может найти корень любой функции; квадратный корень — это особый случай, когда используется уравнение «y = x²-S», когда x является квадратным корнем из S, тогда y становится равным 0.
Приведенное ниже уравнение дает линейное приближение.
В нашем случае f(x) = x² — S, поэтому f’(x) = 2x.
Подставив приведенные выше значения в уравнение, можно записать как
где S — число, для которого нам нужно найти квадратный корень, а x — приближение квадратного корня.
В итерации мы можем начать с предположения, которое обычно равно S/2, а затем применить описанную выше итерацию для x1, x2, x3 и так далее, пока не добьемся необходимой точности. Программистам может быть сложно объяснить коллегам, что происходит. Два других метода, описанные ниже, более логичны, чем математически.
Ниже приведен листинг, реализующий итерацию Ньютона-Рафсона.
Вавилонский метод.
Вавилонский способ вычисления квадратного корня — очень логичный метод, использующий среднее арифметическое предположения квадратного корня из S, скажем «а», и отношения (S/a).
Если а является завышенной оценкой квадратного корня из S, то S/a является заниженной оценкой квадратного корня из S, и наоборот. Тогда среднее значение S/a и a будет лучшим приближением квадратного корня из S.
Путем итерации с новыми приближениями оценка становится лучше. Ниже приведен листинг кода для нахождения квадратного корня функции.
Метод программистов.
Это самый прямой, если не оптимальный способ нахождения квадратного корня числа.
Алгоритм начинается с проверки нижней границы (lo) как нуля и верхней границы (hi) как самого числа (S). Затем на каждой итерации он устанавливает mid = lo + (hi-lo)/2 и проверяет, больше ли mid², чем S, или меньше, чем S. На основе этого сравнения корректируется нижняя или верхняя граница, а затем снова корректируется середина на основе новой нижней или верхней границы. Мы можем повторять итерацию до требуемой точности.
Если вам интересно, это похоже на известный алгоритм, да, вы правы, это не что иное, как бинарный поиск квадратного корня в линейном пространстве квадратично возрастающей функции Х². Из всех известных мне методов (это небольшое подмножество) этот более логичен для понимания и объяснения.
Ниже приведен список для того же самого.
Я надеюсь, что это было полезно.
Ниже приведена суть кода драйвера для всех трех методов.
Спасибо за чтение.
Следуйте за мной для получения дополнительных статей по программированию.
