Algorithm for finding a zero point

I have following challenge:

Implement a function that searches for a null point of 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.

1. Find a condition to decide in which halved interval the search has to be continued. So after cutting the interval into two intervals we have to choose one to get on with our search.

2. We assume that there is just one zero point in the interval between a and b.

I am struggling with point 1. I already had some questions on that topic that helped me a lot but now I need to implement it in java but it is not working yet.

Here is my code so far:

private static double nullstelle(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(sin > 0){
                result =开发者_高级运维 nullstelle(a, middle);
            }else{
                result = nullstelle(middle, b);
            }
        }
        return result;
    }

I tried to implement using recursion but maybe an other way would be better, I don't know. Any ideas?

If there is just one zero point between a and b, that means sign(sin(a)) != sign(sin(b)). In replacing a or b with your mid-point, you'll need to make sure this remains the case by doing something like this:

if (sign(sin(a)) == sign(sin(middle)))
    result = nullstelle(middle, b);
else
    result = nullstelle(a, middle);

with sign(x) defined as

int sign(double x) { return x >= 0 ? 1 : -1; }

Since there is at most one zero-crossing in our considered interval, there are three possibilities:

1. Zero point is in the left half
2. Zero point is in the right half
3. The bisection is the zero point.

If the bisection point is the zero point, you're done.

Otherwise, the segment that contains the zero crossing must have different signs on its endpoints.

Recurse on the segment that has different signs on its endpoints

You almost got it correct. You choose the interval based on the sign change - if the sign changes between the left and right bound of the interval, you choose that interval:

private static double nullstelle(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(sin == 0) {  // Rare case but might happen
                result = middle;
            } else if (Math.signum(sin) != Math.signum(b))  { // The sign changes between middle and b
                result = nullstelle(middle, b);
            } else if (Math.signum(sin) != Math.signum(a))  { // The sign changes between a and middle
                result = nullstelle(a, middle);
            } else  {
              // Throw an exception here, the sin function does not cross x axis in the given interval
            }
        }
        return result;
    }

Note also that the function might cross the x axis more times in the given interval. Then the signum might change in both intervals and this function will pick only the right one (middle to b) and you will lose some of the solutions.

given x in [a,b] abounded interval (a<=x<=b) we can say that an application f:[a,b]->R has a root on [a,b] i.e there is an x in the bounded interval [a,b] that satisfies f(x)=o if and only if f(a)*f(b)<0.

In simple words there is a root on the interval is the sign of the function changes on that interval.

In order to find that point we would use the binary partitioning of the interval.

I would modify this code as it follows:

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

        if(Math.abs(a-b) < 0.0001){
            return middle;
        }
        if(Math.sin(a)*Math.sin(middle)<0) {
            return nullstelle(a, middle);
        }
        if(Math.sin(middle)*Math.sin(b)<0) {
            return nullstelle(middle, b);
        }
    }