Algorithms Question (Bisection Method & Sqrt)

[apcxpc]

Hi all

Here is a question from my assignment in Algorithms & Complexity Theory. I'm having a problem with part 2.

A continuous function f(x) such that f(a) and f(b) have opposite signs must have a zero (a point x such that f(x)=0) in the interval [a,b]. By checking whether the zero occurs in the subinterval [a,(a+b/2] or the subinterval [(a+b)/2,b].
The bisection method for approximating a zero of f(x) is based on repeating this process until a zero is obtained to within a predescribed error.

1. Give pseudocode for the bisection method algorithm Bissec(f(x),a,b,error) for finding an approxmiation to a zero of a continuous function f(x) in the interval [a,b] accurate to within error.

2. Show how to use the bisection method of (a) to compute sqrt(c) of a positive number c. Give pseudocode for the bisection method algorithm BissecSQRT(c,error) for finding the square root of a number c accurate to within error.

My answer to part 1 is as follows:

int Bissec(f(x), a, b, error){

   repeat{
    x = (a+b)/2;
    if (f(x)==0) return x;
    else if (((f(a)>0)&&(f(x)>0)) || ((f(a)<0)&&(f(x)<0))) a = (a+b)/2;
    else if (((f(a)>0)&&(f(x)<0)) || ((f(a)<0)&&(f(x)>0))) b = (a+b)/2;
   } until ((b-a)<error)
   return x;
}

I'm completely stuck with the second question. Would greatly appreciate any help/tips/guidance. :o

[indianscorpion2]

take the equation as f(x)= x^2-c=0.
take two initial guesses a,b such that f(a) and f(b) are on either side of zero.narrow down the guesses recursively.till you reach suitable accuracy.

[apcxpc]

Thanks for the reply indianscorpion.

So I'm thinking the BissecSQRT algorithm runs only once and looks sort of like this:

int BissecSQRT(c, error){

f(x) = x^2 - c;
//choose some a and b such that f(a)> 0 and f(b)<0
x = Bissec(f(x),a,b,error);
return x;
}

The problem I'm having is that, in a later question I will have to compare the efficiency (number of iterations) of the BissecSQRT algorithm with another SQRT algorithm (but the BissecSQRT method will run only once, so it's the number of iterations of the Bissec method that matter).... so I can't take arbitrary guesses a and b as the initial starting point. How do I choose an optimal a and b?

[Rashakil Fol]

Use 1 and c as your starting points; they'll always work, because the square root will always be between them. You can't really pick any fraction of c, like c/2, without testing its resulting sign first. And if you do that, well, you've already started the bisection process. So 1 and c work. Remember that c might be less than 1.

Those guesses aren't "optimal," because the optimal starting point would be the square root itself. So there's no need to look for optimal starting points -- just ones guaranteed to work all the time.

[apcxpc]

Hellos

Thanks Rashakil.

I tried implementing it that way. We then had to compare the efficiency (number of iterations) of the BissectionSQRT method with that of another sqrt method. I tried this, and ran into an odd problem.

If c = 100 and error = 0.00001 (the inputs we had to compare the different efficiencies for) then both methods return proper results.

If c = 5000 and error=0.00001, the BissectionSQRT method returns a sqrt that is very close to the exact answer, but not within 0.00001 of it. But I defined the BissectionSQRT method to return a value within the given error.
Could someone please have a look at my code, and let me know what I'm doing wrong?

class Function {
    double c;
    String func;

    public Function(String F, double C){
        c = C;
        func = F;
    }

    public double solve(double x){
        //the function (x^2 - c) has been hard-coded in for convenience
        if (func.equals("x^2-c")) return (x*x - c);
        else return 0;
    }
}


public class Test {

    public static double BabylonianSQRT(double a, double error){
        double x = a;
        int count=0;
        while (Math.abs(x-a/x)>error){
            count++;
            x = (x + a/x)/2;
        }
        System.out.println("Num iterations in BabylonianSQRT method: "+count);
        return x;
    }


    public static double Bissec(Function f, double a, double b, double error){
        double x=0;

        int count=0;

        do {
            count++;
            x = (a+b)/2;
            if (f.solve(x)==0) return x;
            else if (f.solve(a)*f.solve(x) > 0) a = x;
            else b = x;     
        }while (Math.abs(b-a)>=error);
        System.out.println("Num iterations in Bissec Method: "+count);
        return x;
    }

    public static double BissectionSQRT(double c, double error){
        Function f = new Function("x^2-c",c);
        //choose a and b such that f(a) and f(b) have opposite signs
        double a = 1;
        double b = c;
        double x = Test.Bissec(f, 1, c, error);
        return x;       
    }




    public static void main(String[] args){

        double x = Test.BissectionSQRT(5000, 0.00001);
        System.out.println("BissectionSQRT: " + x);

        System.out.println();

        double y = Test.BabylonianSQRT(5000, 0.00001);
        System.out.println("BabylonianSQRT: " + y);
    }
}

The output was...

Num iterations in Bissec Method: 29
BissectionSQRT: 70.71068377606571

Num iterations in BabylonianSQRT method: 10
BabylonianSQRT: 70.71067811869202

[apcxpc]

ah ok... nevermind...

The square root itself is within error of the correct sqrt, not the sqrt^2 being within error of the correct square.

Don't mind me. :o

Thanks again for the help, guys.