Реализуйте свою функцию нахождения квадратного корня

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

Решение

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

Допустим, что нам нужно извлечь квадратный корень из числа x. Установим левую границу бинпоиска на 0, а правую — на max(1, x). Таким условием мы учтем все возможные случаи: на отрезке 0..1 корень из числа больше самого числа, на отрезке 1..inf — меньше).

Теперь найдем среднее арифметическое границ, назовем его m, и проверим, больше ли m * m, чем x. Если да, то искомый ответ лежит на числовой прямой левее m, а значит, необходимо сделать m правой границей бинпоиска, иначе — левой. Спустя пару сотен таких итераций мы найдем квадратный корень с удовлетворяющей всем потребностям точностью.

Бонус с повышенной сложностью

Реализуйте подобным образом функцию для поиска корня n-ной степени.