perfect square prob... math?

[skeptik]

I need a function to check an inputed number if can be perfectly squared. Just checking the last two digits makes this possible.

00
01
04
09
16
21
24
25
29
36
41
44
49
56
61
64
69
76
81
84
89
96

i have found references to such functions (issquare), but no source. if someone could help me out that would be great.

i have thought about parsing the last two digits and checking them against an array of the above possibilities. i am just not sure of the best solution. please help me construct something.

thanks,
skeptik

(i hope this makes sense.)

[Salem]

> Just checking the last two digits makes this possible.
Depends which way you want to go

You can convert the input number ("1234") to an integer (1234), then do modulo 100 on it to extract the last 2 digits (x%100).

Or you can leave it as a string, and create a pointer to the last pair of characters
char *last2 = &string[ strlen(string)-2 ];

The rest is a table search to compare against your list

[Unregistered]

The last two digits(in base 10) of a positive number can be easily obtained as
i-(i/100)*100
or i%100
no parsing required

If a number is square , then the remainder upon division by 4 is either 0 or 1 , since any multiple of 100 is divisble by 4 , the last two digits (in base ten) of a square number must leave a remainder of 0 or 1 upon division by 4 , but unfortunately this only can be used to reject numbers which are not squares , it cannot be used to determine whether a number is square or not .
so you can use this,
but note the remainder of the divison of i by 4 is simply i&3

int issquare(int i)
{
int j;
if(i<0) return 0;
j= i&3;
if( (j != 0) && (j!=1) ) return 0; /*weeding out the obvious non squares*/
/*check if square, ugly brute force method */
if ( i&1 ) for(j=1;j*j<i;j+=2); /*i is odd check only odd numbers */
else for(j=0;j*j<i;j+=2); /*check only even*/
return (j*j==i);
}

another method that comes into my mind is by using the fact that the sum of first n odd numbers is n*n
so we have
int issquare1(int i)
{
int j,s=0;
if(i<0) return 0;
j=i&3;
if( (j!=0) && (j!=1) ) return 0; /*weeding out the obvious non squares*/
for(j=1;s<i;j+=2) s+=j;
return (s==i);
}

the above method requires no multiplication


since the square is a monotonic function we can also use binary search

int issquare2( int i)
{
int j,lo,hi,mid;
if(i<0) return 0;
j=i&3;
if( (j!=0) && (j!=1) ) return 0; /*weeding out the obvious non squares*/
if(i<=1) return 1;
for(lo=0,hi=i;lo+1<hi; )
{
mid=(lo+hi)/2;
if( mid*mid>i) hi=mid;
else lo=mid;
}
return (lo*lo==i);
}


Anyway last two digits do not determine wheter a number is square or not for eg. in base 10, 16 is a square , 116 is not . However sometimes they can tell if a number is not a square .
For , eg a number having 06 as the last two digits in base 10 cannot be a square .

Originally posted by skeptik
I need a function to check an inputed number if can be perfectly squared. Just checking the last two digits makes this possible.

00
01
04
09
16
21
24
25
29
36
41
44
49
56
61
64
69
76
81
84
89
96

i have found references to such functions (issquare), but no source. if someone could help me out that would be great.

i have thought about parsing the last two digits and checking them against an array of the above possibilities. i am just not sure of the best solution. please help me construct something.

thanks,
skeptik

(i hope this makes sense.)