n-й корневой алгоритм

Question

Какой самый быстрый способ вычислить n -й корень числа?

Мне известен метод Try and Fail, но мне нужен более быстрый алгоритм.

Answer 1

Канонический способ сделать это - Метод Ньютона .Если вы не знаете, производная от x ⁿ равна nx ^n-1 .Это пригодится.1 хорошая первая догадка.Вы хотите применить его к функции a - x ⁿ

IIRC, она суперконвергентна с функциями вида a - x ⁿ , но в любом случае это довольнобыстро.Кроме того, IIRC, предупреждение в вики о том, что оно не сходится, будет применяться к более сложным функциям, обладающим свойствами, которых не хватает интересующим вас «приятным» функциям.

Answer 2

Не самый быстрый, но работает.Замените выбранный вами тип:

    private static decimal NthRoot(decimal baseValue, int N)
    {
        if (N == 1)
            return baseValue;
        decimal deltaX;
        decimal x = 0.1M;
        do
        {
            deltaX = (baseValue / Pow(x, N - 1) - x) / N;
            x = x + deltaX;
        } while (Math.Abs(deltaX) > 0);
        return x;
    }

    private static decimal Pow(decimal baseValue, int N)
    {
        for (int i = 0; i < N - 1; i++)
            baseValue *= baseValue;
        return baseValue;
    }

Answer 3

Вы имеете в виду n-й корневой алгоритм ? Это не метод проб и ошибок, а итеративный алгоритм, который повторяется до тех пор, пока не будет достигнута требуемая точность.

Answer 4

Извлечение корня n с помощью ведической математики - самый быстрый метод.Подробнее об алгоритме см. http://www.vedicmaths.org/Journal.asp