Q. Finding integer square root of an element N (we are doing here it by 3 methods)

METHOD  1 (Naive)

It  is  naive  method  which  is  in  your  mind  in  which  we  check  every  value  from  1  to n    square  its  value  to  check  it  equal  to  N

PseudoCode

for(int i=0 to N)

{

if(i*i==N)

print  i  is  the  square  root

if(i*i>N)

print  Square  root  is  not  integer

}

Time =O(n)

METHOD  2 (Newton Raphson)

It  is  Newton - Raphson  method  as  we  can  see  that  sum  of  N  odd  terns  result  into  N^2

It  says  that  the  N consecutive  odd  elements  add  upto  give  N^2  as  its  result  as  we  can  see

1+3=4(i.e  2^2)    [2  consecutive  odd  elements  add  upto  give  4 i.e  2^2]

1+3+5+7+9+11=36(i.e  6^2)   [6  consecutive  odd  elements  add  upto  give  36 i.e  6^6]

The  programmers  having  some  knowledge  of  Mathematics  will  work  that  out  also

#include<stdio.h>

int square(int);

int square(int a)

{

int sum=0;

for(int k=0;k<a;k++)

sum+=2*k+1;

return sum;

}

int main()

{

int N;

printf("Enter  the  value  of  N");

scanf("%d",&N);

for(int k=1;k<N;k++)

{

if(square(k)==N)

{printf("%d is our answer",k);return 0;}

}

printf("No integer value is found");

return 0;

}

Time=O( sqrt(N) );

METHOD  3 (Binary  Search)

It  will  be  the  most  expected  answer  as  of  having  less  complexity  than  above

  low=0; high=N;

while

{

 mid=(low+high)/2;

if(mid*mid>N)

high=mid;

if(mid*mid==N)

done;

if(mid*mid<N)

low=mid;

if(low==high)

break;

}

print  no  result

Time=O(log n)

This  can  be  extended  for  finding  square  root  in  decimals  also

See  this  http://ideone.com/ePF12g  for  the  result

Please  tell  any  queries.......