# 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
```