recrsion square root

[android_gl]

how to test if a num is a square root?
ex: 9 is square root
    3 is not square root


    /////////////////////////////////////////////
    //do not worry about sytax. 



    int x = 0; //always start at 0
    int y = 101010;  //is this a square root?
    square(x, y){
         if((x*x) >= y){       //not a square root
             return false;
         }
         else if((x*x) == y)    //it is a square root
             return true;
         }
         else{                 //inc x by 1
            square(x+1, y);
         }
    }



this algorithm works fine when y is small int. ex 4, 10, 20.
but when i put y to be large ex 10000. than i get it to problem.
this is bc x start out with 0 and slowing get inc by 1. this takes alot of time.

is there better way to do this by using recursion? may be there is some formula that i dont know about.

[ddanbe]

I wonder what happens when y=4(=square) and x happens to become 2?
Your function would return false I guess. Look at line 14.

[JamesCherrill]

is there better way to do this by using recursion? may be there is some formula that i dont know about.

Instead of just true/false you could define the method to return three values for to small/just right/ too big (eg see the Comparator interface in the API). Then you could do a kind of binary search for x - start with very large steps and home in with ever smaller steps as you get closer.

[cwarn23]

I believe the IBM guess and go algorithm which was invented in either the 1980's or the 1990's was a successful square root algorithm which is quote simple actually. As simple as the logic is it can be a pain to code so I shall explain.

Basically you get the number which needs to be rooted and devide by 2. We will call this x. Then check if xx=original number. If fails then check if bigger or smaller than original number. If bigger than x=0.5 and check again or if smaller than x*=1.5

This process of checking and multiplying is repeated until the correct answer is found. It may not be efficient for large numbers but it sure is efficient for 32-bit which is what IBM was dealing with at the time. So if you're planning to make a square root function/method you may wont to take this sort of algorithm into consideration.