# N-th root of a number

Given two numbers N and A, find N-th root of A. In mathematics, Nth root of a number A is a real number that gives A, when we raise it to integer power N. These roots are used in Number Theory and other advanced branches of mathematics.
Examples:

Input : A = 81
N = 4
Output : 3
3^4 = 81

As this problem involves a real valued function A^(1/N) we can solve this using Newton’s method, which starts with an initial guess and iteratively shift towards the result.
We can derive a relation between two consecutive values of iteration using Newton’s method as follows,

according to newton’s method
x(K+1) = x(K) – f(x) / f’(x)
here    f(x)  = x^(N) – A
so    f’(x) = N*x^(N - 1)
and     x(K) denoted the value of x at Kth iteration
putting the values and simplifying we get,
x(K + 1) = (1 / N) * ((N - 1) * x(K) + A / x(K) ^ (N - 1))

Using above relation, we can solve the given problem. In below code we iterate over values of x, until difference between two consecutive values of x become lower than desired accuracy.

Below is the implementation of above approach:

## C++

br>
 // C++ program to calculate Nth root of a number #include using namespace std;    //  method returns Nth power of A double nthRoot(int A, int N) {     // intially guessing a random number between     // 0 and 9     double xPre = rand() % 10;        //  smaller eps, denotes more accuracy     double eps = 1e-3;        // initializing difference between two     // roots by INT_MAX     double delX = INT_MAX;        //  xK denotes current value of x     double xK;        //  loop untill we reach desired accuracy     while (delX > eps)     {         //  calculating current value from previous         // value by newton's method         xK = ((N - 1.0) * xPre +               (double)A/pow(xPre, N-1)) / (double)N;         delX = abs(xK - xPre);         xPre = xK;     }        return xK; }    //    Driver code to test above methods int main() {     int N = 4;     int A = 81;        double nthRootValue = nthRoot(A, N);     cout << "Nth root is " << nthRootValue << endl;        /*         double Acalc = pow(nthRootValue, N);         cout << "Error in difference of powers "              << abs(A - Acalc) << endl;     */        return 0; }

## Java

 // Java program to calculate Nth root of a number class GFG {            // method returns Nth power of A     static double nthRoot(int A, int N)     {                    // intially guessing a random number between         // 0 and 9         double xPre = Math.random() % 10;                // smaller eps, denotes more accuracy         double eps = 0.001;                // initializing difference between two         // roots by INT_MAX         double delX = 2147483647;                // xK denotes current value of x         double xK = 0.0;                // loop untill we reach desired accuracy         while (delX > eps)         {             // calculating current value from previous             // value by newton's method             xK = ((N - 1.0) * xPre +             (double)A / Math.pow(xPre, N - 1)) / (double)N;             delX = Math.abs(xK - xPre);             xPre = xK;         }                return xK;     }            // Driver code     public static void main (String[] args)     {         int N = 4;         int A = 81;                double nthRootValue = nthRoot(A, N);         System.out.println("Nth root is "          + Math.round(nthRootValue*1000.0)/1000.0);                /*             double Acalc = pow(nthRootValue, N);             cout << "Error in difference of powers "                 << abs(A - Acalc) << endl;         */     } }    // This code is contributed by Anant Agarwal.

## Python3

 # Python3 program to calculate # Nth root of a number import math import random    # method returns Nth power of A def nthRoot(A,N):        # initially guessing a random number between     # 0 and 9     xPre = random.randint(1,101) % 10         #  smaller eps, denotes more accuracy     eps = 0.001         # initializing difference between two     # roots by INT_MAX     delX = 2147483647         #  xK denotes current value of x     xK=0.0         #  loop untill we reach desired accuracy     while (delX > eps):            # calculating current value from previous         # value by newton's method         xK = ((N - 1.0) * xPre +               A/pow(xPre, N-1)) /N         delX = abs(xK - xPre)         xPre = xK;                return xK    # Driver code N = 4 A = 81 nthRootValue = nthRoot(A, N)    print("Nth root is ", nthRootValue)    ## Acalc = pow(nthRootValue, N); ## print("Error in difference of powers ", ##             abs(A - Acalc))    # This code is contributed # by Anant Agarwal.

## C#

 // C# program to calculate Nth root of a number using System; class GFG {            // method returns Nth power of A     static double nthRoot(int A, int N)     {         Random rand = new Random();         // intially guessing a random number between         // 0 and 9         double xPre = rand.Next(10);;                // smaller eps, denotes more accuracy         double eps = 0.001;                // initializing difference between two         // roots by INT_MAX         double delX = 2147483647;                // xK denotes current value of x         double xK = 0.0;                // loop untill we reach desired accuracy         while (delX > eps)         {             // calculating current value from previous             // value by newton's method             xK = ((N - 1.0) * xPre +             (double)A / Math.Pow(xPre, N - 1)) / (double)N;             delX = Math.Abs(xK - xPre);             xPre = xK;         }                return xK;     }            // Driver code     static void Main()     {         int N = 4;         int A = 81;                double nthRootValue = nthRoot(A, N);         Console.WriteLine("Nth root is "+Math.Round(nthRootValue*1000.0)/1000.0);     } }    // This code is contributed by mits

## PHP

 \$eps)     {         // calculating current         // value from previous         // value by newton's method         \$xK = ((int)(\$N - 1.0) *                       \$xPre + \$A /                       (int)pow(\$xPre,                                \$N - 1)) / \$N;         \$delX = abs(\$xK - \$xPre);         \$xPre = \$xK;     }        return floor(\$xK); }    // Driver code  \$N = 4; \$A = 81;    \$nthRootValue = nthRoot(\$A, \$N); echo "Nth root is " ,        \$nthRootValue ," ";    // This code is contributed by akt_mit ?>

Output:

Nth root is 3