By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
455,804 Members | 1,358 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 455,804 IT Pros & Developers. It's quick & easy.

recursion square root

P: 59
how to test if a num is a square root?
ex: 9 is square root
3 is not square root
/////////////////////////////////////////////
Expand|Select|Wrap|Line Numbers
  1. x = 0; //always start at 0
  2. y = 101010;  //is this a square root?
  3. square(x, y){
  4.      if((x*x) >= y){       //not a square root
  5.          return false;
  6.      }
  7.      else if((x*x) == y)    //it is a square root
  8.          return true;
  9.      }
  10.      else{                 //inc x by 1
  11.         square(x+1, y);
  12.      }
  13. }
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.
Sep 14 '13 #1
Share this Question
Share on Google+
3 Replies


Expert 100+
P: 1,043
change the increment part.....

start with increments of i.e. 100
if x*x>y (not x*x>=y), than do :
x=x-100, and change increments to 10

or, if google, and find this
Sep 14 '13 #2

P: 59
i am not sure how to do this part: x=x-100, and change increments to 10

Expand|Select|Wrap|Line Numbers
  1. x = 100; //always start at 0
  2. y = 101010;  //is this a square root?
  3. square(x, y){
  4.      if((x*x) > y){       //not a square root
  5.          return false;
  6.      }
  7.      else if((x*x) == y)    //it is a square root
  8.          return true;
  9.      }
  10.      else{                 //inc x by 1
  11.         square(x+1, y);
  12.      }
  13. }
Sep 14 '13 #3

Nepomuk
Expert 2.5K+
P: 3,112
Well, there are a few things you could do. Personally, I'd have a look at the so called Babylonian method for computing square roots; it's quite simple and relatively easy to implement in a recursive manner. Also, it should be much faster than your current method.
Sep 14 '13 #4

Post your reply

Sign in to post your reply or Sign up for a free account.