Алгоритм вычисления корня n-ой степени из произвольного положительного числа

Наткнулся на интересную задачку: Дано действительно число a и натуральное число n. Вычислите корень n-ой степени из числа без использование библиотек.

Входные данные: число a — действительное, неотрицательное, не превосходит 1000, задано с точностью до 6 знаков после запятой. Число n — натуральное, не превосходит 10.
Выходные данные: Программа должна вывести единственное число: ответ на задачу с точностью не менее 5 знаков после запятой.

Естественно было интересно решить её на черновике карандашом, а потом начеркать в редакторе и попробовать скомпилировать. Без гугления, подсказок и тем более использования библиотек. Если вы решаете такое в первый раз, то попробуйте сначала написать программку для нахождения обычного квадратного корня. Если вам кажется задача сложной, решите почти такую же, но попроще. Тогда у вас уйдет страх и возникнет какое-то примерное понимание.

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

/* Calculating the square root by iterations */
 
#include <stdio.h>
 
int main(void) {
    double num = 570.15;
    double root = num / 2;
    double eps = 0.01;
    int iter = 0;
    while( root - num / root > eps ){
        iter++;
        root = 0.5 * (root + num / root);
        printf("Iteration: %d : root = %f\n", iter, root);
    }
    printf("root = %f", root);
    return 0;
}

Запустить код можно тут: КЛИК

Логарифмическая сложность алгоритма? Или другая? :)

Теперь уже можно переходить к усложненному варианту задачи. В этом случае решение получается более обобщенным.

#include <stdio.h>
 
double mabs(double x){ return (x < 0)? -x : x; }
 
int main(void) {
    double num = 8;
    int rootDegree = 3;
 
    printf("Число, корень которого считаем а = %f\n", num);
    printf("Корень степени n = %d\n", rootDegree);
   
    double eps = 0.00001;             //допустимая погрешность
    double root = num / rootDegree;   //начальное приближение корня
    double rn = num;                  //значение корня последовательным делением
    int countiter = 0;                //число итераций
    while(mabs(root - rn) >= eps){
        rn = num;
        for(int i = 1; i < rootDegree; i++){
            rn = rn / root;
        }
        root = 0.5 * ( rn + root);
        countiter++;
    }
   
    printf("root = %f\n", root);
    printf("Число итераций = %i\n", countiter);
   
    return 0;
}

Запустить код можно тут: КЛИК

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

Это первый рабочий алгоритм, написанный на коленке. Нужно еще поразмышлять о сложности и возможностях ускорения. Кстати, какие возможности ускорения этого алгоритма можно реализовать на ваш взгляд?

Чувствую, что будет вопрос: «Зачем это делать, если всё реализовано в библиотеках сто лет назад?!»

Ответ: Лично мне всегда нравилось думать над алгоритмами, которые уже реализованы в стандартных библиотеках. Пытаться разработать их самостоятельно (ну или разработать какую-нибудь медленно работающую пародию и потерпеть неудачу). Это очень хорошо тренирует мозг. Поэтому, на мой взгляд, «изобретать велосипед» очень полезно. И категорически вредно всегда пользоваться всем готовым, не имея никакого представления о внутреннем устройстве.