Nth Root Of M

Posted: 2 Jan, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

You are given two positive integers N and M. You have to find the Nth root of M i.e. M^(1/N).

Note:
N'th root of an integer M is a real number, which when raised to the power N gives M as a result.

N'th root of the M should be correct up to 6 decimal places.
Input Format:
The first line of the input contains an integer T denoting the number of test cases.

The first and only line of each test case consists of two space-separated integers N and M.
Output Format:
For each test case, print a real number with precision till 6 decimal places that denote the Nth root of M in a separate line.
Note:
You don't have to print anything, it has already been taken care of. Just Implement the given function.
Constraints:
1<= T <= 10^3
1<= N <= 300
1<= M <= 10^15

Time Limit: 1 sec.
Approach 1
  • Let’s say X is the Nth root of M.
    • X = M ^ (1 / N)
  • The above equation can be written as follows:
    • X ^ N = M
    • X ^ N - M = 0
    • Let’s assume F(X) = X ^ N - M
  • Now we need to find the root of this equation, for which we can use the Newton Raphson method to solve this equation.
  • In Newton's Raphson method we start with an initial guess value of X (any random initial value is fine) and iterate through a process that takes us towards the actual solution of the equation.
    • Let’s say X(0) is the initial guess value.
    • The relationship between the current value of solution value x(k) and the solution of the equation in the next iteration X(K + 1) is as follows:
      • X(K + 1) = X(K) - F(X(K)) / F'(X(K)), where F'(X(K)) denotes the value derivative of F(X) at X = X(K).                                    ....(1)
    • In the given case F'(X(k)) = N * X(K) ^ N - 1.
    • So equation (1) can be written as follows:
      • X(K + 1) = X(K) - (X(K) ^ N - M) / (N * X(K) ^ N - 1)
      • X(K + 1) = (X(K) * (N * X(K) ^ N - 1) - X(K) ^ N + M) / (N * X(K) ^ N - 1))
      • X(K + 1) = (X(K) ^ N * (N - 1) + M) / (N * X(K) ^ N - 1)
  • So using the above formula to calculate new possible solution value X. Till the gap between X(K + 1) and X(K) become less than 10-7.
  • When this condition is reached we get our required solution.
Try Problem