I need to find the value of x when x^x = N, N is a value inputted. Let's assume N is 27. In this example, the x value would be 3, since the cube root of 27 is 3, or 3³ = 27. If N is 256 then x would be 4, since 4⁴ = 256.

I need to figure out a recursive program that figures out the value of x. This is what I have so far:

public static void main(String[] args) {
    
    Scanner n = new Scanner(System.in);

    System.out.println("Enter a number");
    double number = n.nextDouble();


}

public static void findXValue(double n) {

    double logn = Math.log(n);
...

The findXValue function uses logs, but it also doesn't work. And I need to use a recursive method as well. Any help would be appreciated

CodePudding user response：

    public static double findXValue(double n) {
        double result = 0.0;
        double number = 0.0;
        while(result <= n) {
            result = Math.pow(number, number);
            if(result == n) {
                return number;
            }

            number  ;
        }

        return -1;
    }

CodePudding user response：

I'm assuming x can be a floating point number, since you didn't say.

You can look at this as the problem of finding a root of the function F(x) = x^x - N. The simplest approach is called bisection, which works something like binary search.

Start with an interval [a, b] such that F(a) and F(b) have opposite signs. For this problem that's always F(a)<0 and F(b)>0 due to the nature of the function. Here if N > 1, start with [1,N]. If 0 <= N < 1, use [N,1]. (If N = 1, then x = 1).

After that, iterate. Compute x = (a b)/2. If F(x) and F(a) have the same sign (negative), then set a=x. Else F(x) must have the same sign as F(b) (positive), so set b=x.

When a and b differ by at most one unit-of-least-precision (smallest floating point difference possible), stop and return a.

This iteration is easy to express as a recursion. I'm not going to give you the answer.

double solve(double a, double b, double n) {
  if (b - a <= ULP) return a;

  // all the fun happens here
}

The same technique will work for integers, but be careful about overflow and roundoff errors when computing the midpoint.

CodePudding user response：

Using Newton's method to approach the root.

import java.util.Scanner;

public class XPowerX {
    static final double PRECISION = 0.00001;
    static final int MAX_RECURSION = 10000;

    public static void main(String[] args) {

        Scanner n = new Scanner(System.in);

        System.out.println("Enter a number");
        double number = n.nextDouble();

        System.out.println(findXValue(number));
    }

    public static double findXValue(double n) {
        double seed = Math.random();
        double y = Math.pow(seed, seed);
        double derivative;
        for(int i = 0; i < MAX_RECURSION; i  ) {
            if (Math.abs(y) <= PRECISION) {
                return seed;
            }

            y = Math.pow(seed, seed);
            derivative = y * Math.log(seed)   y;
            y -= n;
            // The derivative is used as the slope of tangent line

            // Newton's method
            seed = seed - y / derivative;

            if(seed < 0) {
                seed = 0;
            }
        }
        return -1;
    }
}

Output:

Enter a number
16
2.7453680235674636

Enter a number
0.8
0.7395336501071896

Enter a number // No real root
0.3
-1.0

Enter a number // Overflow (NaN)
125000
-1.0