Find zero points with recursion

I want to find the zero points of a sine function. The parameter is a interval [a,b]. I have to it similar to binary search.

Implement a function that searches for null points in the sinus function in a interval between a and b. The search-interval[lower limit, upper limit] should be halved until lower limit and upper limit are less then 0.0001 away from each other.

Here is my code:

public class Aufg3 {
    public static void main(String[] args) {

        System.out.println(zeropoint(5,8));
    }

    private static double zeropoint(double a, double b){
        double middle = (a + b)/2;

        if(Math.sin(middle) <开发者_如何学编程 0){
            return zeropoint(a,middle);
        }else if(Math.sin(middle) > 0){
            return zeropoint(middle,b);
        }else{
            return middle;
        }       
    }
}

It gives me a lot of errors at the line with return zeropoint(middle,b);

In a first step I want to find just the first zero point in the interval.

Any ideas?

---

Fundamental problems that everybody has overlooked:

• we don't always want to return a result (imagine finding the zero points of the sine function between pi/4 and 3pi/4, there aren't any).
• in any arbitrary range range there may be several zeros.

Clearly what is needed is a (possibly empty) set of values.

So pseudocode of the function really asked for (not using Java as this is homework):

Set zeropoint(double a, double b)
{
    double middle = mid point of a and b;
    if a and be less than 0.0001 apart
    {
        if (sin(a) and sin(b) are on opposite sides of 0)
        { 
            return set containing middle
        }
        else
        {
            return empty set
        }
    }
    else
    {
        return union of zeropoint(a, middle) and zeropoint(middle, b)
    }
} 

---

Simply saying "it gives me errors" is not very helpful. What kind of errors? Compile errors or uncaught exceptions at runtime?

For your code, two things stand out as possible problems:

1. the variable mitte does not appear to be declared anywhere.
2. you are using > and < to compare reals. While that is ok by itself, it is better to check for 0 using a tolerance instead of relying on < and >, to avoid problems due to floating point precision. For all practical purposes -0.000000000001 is 0.

There might be other problems as well, I just wrote down the ones that jumped out at first glance.

Edit:

Apparently the mitte was due to an error in pasting the code by the OP (and has since been corrected). As other answers have pointed out, the code falls in to infinite recursion. This is because the recursion calls are on the wrong intervals.

One thing to note, the sin function can be monotonically increasing for one choice of a and b, and monotonically decreasing at some other interval. e.g. It is increasing over [0,pi/2] and it is decreasing over [pi/2,3*pi/2]. Thus the recursive calls need to changed according to the original interval the search is being made in. For one interval Math.sin(middle)<0 implies that Math.sin(x)<0 for all x in [a,middle], but for some other interval the opposite is true. This probably why this falls into infinite recursion for the interval that you are trying. I think this works over some other interval where sin is actually decreasing. Try calling your function over [pi/2,3*pi/2].

---

I'm guessing you are getting stack overflow errors at runtime. The < and > signs are reversed. Also, you should use .0001 and not 0 to compare to.

Edit 1: Actually, your basic algorithm has issues. What happens if there are more than one zero in the interval? What happens if sin(a) and the sin(mitte) have the same sign? What happens if there are no zeros in the interval?

Edit 2: Ok, so I did the problem and fundamentally, your solution is problematic; I would try to start over in thinking how to solve it.

The major issue is that there could be multiple zeros in the interval and you are trying to find each of them. Creating a function that returns a type double can only return one solution. So, rather than creating a function to return double, just return void and print out the zeros as you find them.

Another hint: You are supposed to continue searching until a and b are within .0001 of each other. Your final solution will not use .0001 in any other way. (I.e, your check to see if you found a zero should not use the .0001 tolerance and nor will it use 0 exactly. Think about how you will really know if you have found a zero when abs(a-b) is less than .0001.

---

Did you read the assignment to the end? It says:

The search-interval[lower limit, upper limit] should be halved until lower limit and upper limit are less then 0.0001 away from each other.

So you can't expect Math.sin(middle) to return exactly zero because of floating point precision issues. Instead you need to stop the recursion when you reach 0.0001 precision.

---

My guess is that you're running into a StackOverflowError. This is due to the fact that you're never reaching a base case in your recursion. (Math.sin(middle) may never equal exactly 0!)

Your exercise says

[...] until lower limit and upper limit are less then 0.0001 away from each other.

So, try putting this in top of your method:

double middle = (a + b)/2;
if (b - a < 0.0001)
    return middle;

---

Besides some floating point problems other have mentioned, your algorithm seems to be based on the implicit assumptions that:

1. sin(a) is positive
2. sin(b) is negative, and
3. sin(x) is a decreasing function on the interval [a,b].

I see no basis for these assumptions. When any of them is false I don't expect your algorithm to work. They are all false when a=5 and b=8.

---

if(Math.sin(mitte) < 0){

Where is mitte declared? Isn't mitte middle?

---

private static double zeropoint(double a, double b){
    double middle = (a + b)/2;
    double result = middle;

    if (Math.abs(a - b) > 0.0001) {
        double sin = Math.sin(middle);
        if (Math.abs(sin) < 0.0001) {
           result = middle;
        } else if (sin > 0) {
           result = zeropoint(a, middle);
        } else {
           result = zeropoint(middle, b);
        }
    }
    return result;   
}

something like this i think - just to fix first errors