Encuentra la raíz enésima de un número usando el método de bisección

Dados dos enteros positivos N y P . La tarea es encontrar la raíz N -ésima de P.

Ejemplos: 

Entrada: P = 1234321, N = 2
Salida: 1111
Explicación: la raíz cuadrada de 1234321 es 1111.

Entrada: P = 123456785, N = 20
Salida: 2,53849

Enfoque: Hay varias formas de resolver el problema dado. Aquí, el siguiente algoritmo se basa en el concepto matemático llamado método de bisección para encontrar raíces. Para encontrar la raíz potencia N -ésima de un número P dado, formaremos una ecuación en x como ( x ^p – P = 0 ) y el objetivo es encontrar la raíz positiva de esta ecuación usando el método de bisección. 

¿Cómo funciona el método de bisección? 
Tome un intervalo (a, b) tal que ya se sabe que la raíz existe en ese intervalo. Después de esto, encuentre la mitad del intervalo y examine el valor de la función y su derivada en x = mitad.

• Si el valor de la función es 0, significa que se encuentra la raíz
• Si el valor de la función es positivo y su derivada es negativa, significa que la raíz está en la mitad derecha.
• Si el valor de la función es positivo y su derivada es positiva, significa que la raíz está en la mitad izquierda.

A continuación se muestra la implementación del enfoque anterior:

// 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;
}

// Java program for the above approach
import java.util.*;
 
class GFG
{
   
  // Function that returns the value
  // of the function at a given value of x
  static double f(double x, int p, double num)
  {
      return Math.pow(x, p) - num;
  }
   
  // calculating the value
  // of the differential of the function
  static double f_prime(double x, int p)
  {
      return p * Math.pow(x, p - 1);
  }
 
  // The function that returns
  // the root of given number
  static 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
  public static void main(String args[])
  {
 
      double P = 1234321;
      int N = 2;
 
      double ans = root(P, N);
      System.out.print(ans);
  }
}
 
// This code is contributed by ihritik

# 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

// C# program for the above approach
 
using System;
 
public class GFG
{
   
  // Function that returns the value
  // of the function at a given value of x
  static double f(double x, int p, double num)
  {
      return Math.Pow(x, p) - num;
  }
   
  // calculating the value
  // of the differential of the function
  static double f_prime(double x, int p)
  {
      return p * Math.Pow(x, p - 1);
  }
 
  // The function that returns
  // the root of given number
  static 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
  public static void Main(string []args)
  {
 
      double P = 1234321;
      int N = 2;
 
      double ans = root(P, N);
      Console.Write(ans);
  }
}
 
// This code is contributed by AnkThon

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

1111

Complejidad temporal: O(log P).
Espacio Auxiliar: O(1).