Perfect square

> How do you write code to determine a perfect square

> for any integer? I understand Math.sqrt();

>

> Thanks

It is in the series of the sum of odd numbers up to a given point

1 = 1

1+3 = 4

1+3+5 = 9

...

The sqrt is an int

And, I'm sure, other methods...

~Cheers

Adeodatusa at 2007-7-9 4:49:47 >

Here's is a binary search method

static boolean perfectSquare(int x){

int lo = 0;

int hi = 0xF7DE;

while(lo + 1 < hi){

int v = (lo+hi)/2;

if(v*v < x) lo = v; else hi = v;

}

return((lo*lo == x || hi*hi == x));

}

I leave it to you to explain why I use the number F7DE to start it off, and why this algorithm gives the correct answer for negative numbers (which are not perfect squares) and to also explain why the expression (lo+hi)/2 does not overflow when squared. And while you're at it why doesn't it end up in an infinite loop?

If you follow all that, you understand this algorithm and I need say no more. On the other hand you don't really need to understand any of that in order to use it.

But in that case, you might properly wonder whether I got any of this right. Did I use the right magic number, does it really work for the full range, and does it really terminate for all input, and is it anything like efficient?

marlin314a at 2007-7-9 4:49:47 >

Here's an algorithm for finding squares in general.

PERFECT SQUARE SIEVE

To test if a number is a perfect square we make use of the fact that it must produce a quadratic residue for every prime. If it does not do this for a single prime it cannot be square.

Take a list of, say, 50 small primes. Call these P1, P2, P3, ...P50.

Assume n is not a perfect square.

Let n = q (mod p) for any prime. The chances that q is a quadratic residue of p is 1/2, since there are (p + 1)/2 quadratic residues (including zero) and (p - 1)/2 nonquadratic residues.

Let n = q (mod P1). The chances of q being a quadratic residue of P1 are 1/2.

Let n = q2 (mod P2). The chances of q2 being a quadratic residue of P2 are 1/2.

1/2 x 1/2 = 1/4.

Let n = q3 (mod P3). The chances of q3 being a quadratic residue of P3 are 1/2.

1/2 x 1/2 x 1/2 = 1/8.

Continue in this way to P50. The chances of a non-square n filtering through the entire sieve is only 1 in 250.

To proove that the chances that q is a quadratic residue is 1/2, consider p consecutive integers for any prime, p. These will be reduce to 0,1,2,...p - 1 modulo p (not necessarily in that order). There will be one integer congruent to zero and (p - 1)/2 congruent to q such that q is a quadratic residue and (p - 1)/2 congruent to r such that r is a nonquadratic residue. So the chances are 1/2 for any given integer.

If n = qi = 0 (mod Pi), Pi|n and it must be that n = 0 (mod Pi^2) if n is a square because each prime divisor of n must occur to an even power in its decomposition into factors. If this is not the case, n cannot be square and it can be rejected on this count alone.

scriptoHeada at 2007-7-9 4:49:47 >