# Find Nth root of a number using Bisection method

Given two positive integers **N** and **P**. The task is to find the **N**th root of **P**.

**Examples: **

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

Input:P = 1234321, N = 2Output:1111Explanation:square root of 1234321 is 1111.

Input:P = 123456785, N = 20Output:2.53849

**Approach: **There are various ways to solve the given problem. Here the below algorithm is based on Mathematical Concept called Bisection Method for finding roots. To find the **N**-th power root of a given number P we will form an equation is formed in** x **as ( **x ^{p} – P = 0** ) and the target is to find the positive root of this equation using the Bisection Method.

**How Bisection Method works? **

Take an interval** (a, b)** such that its already known that the root is existing in that interval. After this find the **mid** of the interval and examine the** **value of function and it’s derivative at **x = mid.**

- If the value of function is 0 that means root is found
- If the value of the function is positive and its derivative is negative that means the root is lying in the
**right half.** - If the value of the function is positive and its derivative is positive that means the root is lying in the
**left half.**

Below is the implementation of the above approach:

## C++14

`// C++ program for above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function that returns the value` `// of the function at a given value of x` `double` `f(` `double` `x, ` `int` `p, ` `double` `num)` `{` ` ` `return` `pow` `(x, p) - num;` `}` `// calculating the value` `// of the differential of the function` `double` `f_prime(` `double` `x, ` `int` `p)` `{` ` ` `return` `p * ` `pow` `(x, p - 1);` `}` `// The function that returns` `// the root of given number` `double` `root(` `double` `num, ` `int` `p)` `{` ` ` `// Defining range` ` ` `// on which answer can be found` ` ` `double` `left = -num;` ` ` `double` `right = num;` ` ` `double` `x;` ` ` `while` `(` `true` `) {` ` ` `// finding mid value` ` ` `x = (left + right) / 2.0;` ` ` `double` `value = f(x, p, num);` ` ` `double` `prime = f_prime(x, p);` ` ` `if` `(value * prime <= 0)` ` ` `left = x;` ` ` `else` ` ` `right = x;` ` ` `if` `(value < 0.000001 && value >= 0) {` ` ` `return` `x;` ` ` `}` ` ` `}` `}` `// Driver code` `int` `main()` `{` ` ` `double` `P = 1234321;` ` ` `int` `N = 2;` ` ` `double` `ans = root(P, N);` ` ` `cout << ans;` `}` |

## Python3

`# python program for above approach` `# Function that returns the value` `# of the function at a given value of x` `def` `f(x, p, num):` ` ` `return` `pow` `(x, p) ` `-` `num` `# calculating the value` `# of the differential of the function` `def` `f_prime(x, p):` ` ` `return` `p ` `*` `pow` `(x, p ` `-` `1` `)` `# The function that returns` `# the root of given number` `def` `root(num, p):` ` ` `# Defining range` ` ` `# on which answer can be found` ` ` `left ` `=` `-` `num` ` ` `right ` `=` `num` ` ` `x ` `=` `0` ` ` `while` `(` `True` `):` ` ` `# finding mid value` ` ` `x ` `=` `(left ` `+` `right) ` `/` `2.0` ` ` `value ` `=` `f(x, p, num)` ` ` `prime ` `=` `f_prime(x, p)` ` ` `if` `(value ` `*` `prime <` `=` `0` `):` ` ` `left ` `=` `x` ` ` `else` `:` ` ` `right ` `=` `x` ` ` `if` `(value < ` `0.000001` `and` `value >` `=` `0` `):` ` ` `return` `x` `# Driver code` `if` `__name__ ` `=` `=` `"__main__"` `:` ` ` `P ` `=` `1234321` ` ` `N ` `=` `2` ` ` `ans ` `=` `root(P, N)` ` ` `print` `(ans)` `# This code is contributed by rakeshsahni` |

## Javascript

`<script>` ` ` `// JavaScript Program to implement` ` ` `// the above approach` ` ` `// Function that returns the value` ` ` `// of the function at a given value of x` ` ` `function` `f(x, p, num) {` ` ` `return` `Math.pow(x, p) - num;` ` ` `}` ` ` ` ` `// calculating the value` ` ` `// of the differential of the function` ` ` `function` `f_prime(x, p) {` ` ` `return` `p * Math.pow(x, p - 1);` ` ` `}` ` ` `// The function that returns` ` ` `// the root of given number` ` ` `function` `root(num, p) {` ` ` `// Defining range` ` ` `// on which answer can be found` ` ` `let left = -num;` ` ` `let right = num;` ` ` `let x;` ` ` `while` `(` `true` `) {` ` ` `// finding mid value` ` ` `x = (left + right) / 2.0;` ` ` `let value = f(x, p, num);` ` ` `let prime = f_prime(x, p);` ` ` `if` `(value * prime <= 0)` ` ` `left = x;` ` ` `else` ` ` `right = x;` ` ` `if` `(value < 0.000001 && value >= 0) {` ` ` `return` `x;` ` ` `}` ` ` `}` ` ` `}` ` ` `// Driver code` ` ` `let P = 1234321;` ` ` `let N = 2;` ` ` `let ans = Math.floor(root(P, N));` ` ` `document.write(ans);` `// This code is contributed by Potta Lokesh` ` ` `</script>` |

**Output**

1111

**Time Complexity:** O(log P).**Auxilliary Space:** O(1).