wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Check for Perfect Square
        
(Message started by: Barukh on Mar 11^th, 2005, 3:30am)

Title: Check for Perfect Square
Post by Barukh on Mar 11^th, 2005, 3:30am

You are given two integers p, q. Device an algorithm to check if the difference of their squares is also a square. There is one restriction: the squares of p, q may become too big to fit into a machine word, and you don't have at your disposal the special software to manipulate "long integers".

Examples:

is_square(5,4) should return 1
is_square(3,2) should return 0

Title: Re: Check for Perfect Square
Post by towr on Mar 11^th, 2005, 4:39am

Can I assume that (say p > q) a*p for small a does fit in a word?

Title: Re: Check for Perfect Square
Post by Barukh on Mar 11^th, 2005, 7:30am

on 03/11/05 at 04:39:24, towr wrote:

Can I assume that (say p > q) a*p for small a does fit in a word?

If a is an integer, then no. ;)

Title: Re: Check for Perfect Square
Post by VincentLascaux on Mar 11^th, 2005, 9:33am

Can we assume that the sum and difference of p and q fits in a word ?

[hide]
The problem is to find if (p-q)(p+q) is a perfect square)
Call a = gcd(p,q), b = (p+q)/a, c = (p-q)/a
The problem is to find if a²bc is a perfect square, or if bc is a perfect square. Since b and c are prime together, the only way bc is a perfect square is if b and c are perfect squares.
So, let's say we have a function bool isPerfectSquare(int), and a function int gcd(int, int), the solution is

int a = gcd(p+q, p-q);
return isPerfectSquare((p+q)/a) && isPerfectSquare((p-q)/a);
[/hide]

Title: Re: Check for Perfect Square
Post by towr on Mar 11^th, 2005, 9:49am

on 03/11/05 at 09:33:02, VincentLascaux wrote:

Can we assume that the sum and difference of p and q fits in a word ?

The difference isn't a problem, but apparantly the sum may be..
(Actually, it'll only take one bit to keep a record in case of overflow, so it shouldn't be much of a problem. But then neither is implementing larger int-structures..)

Title: Re: Check for Perfect Square
Post by VincentLascaux on Mar 11^th, 2005, 11:43am

In my solution, I only use (p+q)/a. Let's assume a>1. (p+q)/a = (p/a) + (q/a) + (p%a + q%a)/a (with integer divisions)
p%a + q%a is in [0, 2a[, so (p%a + q%a)/a in {0, 1}.
To get that value, we must check is p%a + q%a >= a, or p%a >= a - q%a (this comparision can be done without overflow).

Finally, (p+q)/a can be substitued with p/a + q/a + (p%a >= a - q%a ? 1 : 0), and this would not overflow as long as a >= 2.

Now the problem left is for a==1: given to numbers prime together, determine if there sum is a perfect square (without summing them).

Title: Re: Check for Perfect Square
Post by John_Gaughan on Mar 11^th, 2005, 1:08pm

Sounds like we need to factor (a*a+b*b), or more precisely, figure out if sqrt (a*a+b*b) is an integer without calculating any intermediate values.

Title: Re: Check for Perfect Square
Post by Leonid Broukhis on Mar 11^th, 2005, 2:52pm

Bah. Just do a Pythagorean triples lookup.

Title: Re: Check for Perfect Square
Post by Barukh on Mar 11^th, 2005, 11:54pm

Well done, Vincent! So, what about co-prime p, q (a = 1)? ;)

on 03/11/05 at 14:52:35, Leonid Broukhis wrote:

Bah. Just do a Pythagorean triples lookup.

Interesting idea... But it's not very space-efficient, don't you think? :P

Title: Re: Check for Perfect Square
Post by VincentLascaux on Mar 12^th, 2005, 3:44am

I wrote that (which is in O(ln(p)+ln(q))). Don't know if something more efficient exists... I believe it can't overflow

Code:

//Returns whether an integer i exists such that
//i*i==a+b in O(ln(a)+ln(b))
bool isSumPerfectSquare(int a, int b)
{
if(a==0 && b==0)
return true;

int l = 1;
int r = sqrt(a)+sqrt(b);
while(l<=r)
{
int middle = (l+r)/2;
int mValue = middle - a/middle - b/middle - (a%middle + b%middle >= middle ? 1 : 0);
if(mValue == 0)
return true;
else if(mValue < 0)
l = middle+1;
else
r = middle-1;
}
return false;
}

The idea is to say f(x)=x-(a+b)/x has only one root : sqrt(a+b) that can be found by a binary search (f'(x)>0)
To compute (a+b)/x, do the same trick : a/x + b/x + (a%x+b%x)/x = a/x + b/x + (a%x >= x - b%x ? 1 : 0)

Title: Re: Check for Perfect Square
Post by VincentLascaux on Mar 12^th, 2005, 3:51am

Everybody would have corrected the int mValue initialization to
int mValue = middle - a/middle - b/middle - (a%middle >= middle - b%middle ? 1 : 0);
to prevent the overflow...

Title: Re: Check for Perfect Square
Post by Barukh on Mar 12^th, 2005, 5:36am

Vincent, did you try your code in action? I did, and it seems to return wrong results. For instance, isSumPerfectSquare(18, 19) returns true.

Besides, I think there is a more efficient solution.

Title: Re: Check for Perfect Square
Post by gniv on Mar 12^th, 2005, 6:02am

For 2 numbers a and b, a+b can only overflow one bit.
If a+b is even (a and b have the same parity), then it has to divide 4. So:
a+b = 4*floor(a/4) + ra + 4*floor(b/4) + rb
= 4*(floor(a/4) + floor(b/4) + (ra+rb)/4)
We can compute without overflow the sum in the parens and check for perfect square.

If a+b is odd and a perfect square, then:
a+b = (s+1)*(s+1) = 4( (s/4)*((s/4)+1) ) + 1
So the idea is to subtract 1 from the odd number (let's say it's b), divide both a and b-1 by 4, and then take floor(sqrt(a/4+(b-1)/4)). The result should be s/4.

Title: Re: Check for Perfect Square
Post by VincentLascaux on Mar 12^th, 2005, 6:23am

You are right, it's wrong...
The correction is here:

Code:

bool isSumPerfectSquare(int a, int b)
{
if(a==0 && b==0)
return true;

int l = 1;
int r = sqrt(a)+sqrt(b);
while(l<=r)
{
int middle = (l+r)/2;
int mValue = middle - a/middle - b/middle - (a%middle >= middle - b%middle ? 1 : 0);
if(mValue == 0 && (a%middle == (middle - b%middle)%middle))
return true;
else if(mValue < 0)
l = middle+1;
else
r = middle-1;
}
return false;
}

The added condition is to check if middle divides (a+b). It's equivalent to (a+b)%middle == 0, but without overflow.
Any hint for the more efficient solution? What's its complexity?

Title: Re: Check for Perfect Square
Post by Barukh on Mar 12^th, 2005, 7:20am

on 03/12/05 at 06:23:22, VincentLascaux wrote:

Any hint for the more efficient solution? What's its complexity?

Hmm, probably I was too fast with my claim... Here's the solution that works partially.

So, we are given p, q with gcd(p, q) = 1. Now, if p is even, return 0. (why?)

If q is odd, then return 1 if both (p-q)/2 and (p+q)/2 are squares.

For the case q is even I miss the solution... :(

Title: Re: Check for Perfect Square
Post by towr on Mar 12^th, 2005, 1:13pm

on 03/12/05 at 07:20:36, Barukh wrote:

So, we are given p, q with gcd(p, q) = 1. Now, if p is even, return 0. (why?)

If p>q, I can see why, but as you haven't stated that's the case: p=4, q=5
(Otherwise it simply follows from the properties of primitive pythagorian triples)

Title: Re: Check for Perfect Square
Post by Barukh on Mar 13^th, 2005, 2:42am

on 03/12/05 at 13:13:54, towr wrote:

If p>q, I can see why, but as you haven't stated that's the case: p=4, q=5

;D

Towr, I tacitly used your assumption from this post:

on 03/11/05 at 04:39:24, towr wrote:

Can I assume that (say p > q) a*p for small a does fit in a word?

Title: Re: Check for Perfect Square
Post by towr on Mar 13^th, 2005, 8:14am

on 03/12/05 at 07:20:36, Barukh wrote:

For the case q is even I miss the solution... :(

Well, 6 out of the 25 remaining cases can be easily dismissed.
If q ends in a 2 or 8, p can't end in a 1 or 3
And if q ends in a 6, p can't end in a 3 or 7

Aside from that I haven't made any headway..

Title: Re: Check for Perfect Square
Post by River Phoenix on May 26^th, 2005, 10:28am

If q is even, then write q=2n, so 4n^2-p^2=a^2 for some a.
a^2 + p^2 = 4n^2

Since a^2 + p^2 is divisible by 4, a and p are clearly both even or both odd. In fact, they must be both even since (2i+1)^2=4i^2+4i+1 is congruent to 1 mod 4, where (2i+1) represents any odd number; thus a^2+p^2 is congruent to 2 mod 4 if a and p are both prime.

So we have shown that a and p are both even, but q was already even, so p and q are both divisible by 2, which contradicts our assumption that p and q are written so as to be relatively prime.

Title: Re: Check for Perfect Square
Post by River_Phoenix on May 26^th, 2005, 10:35am

"If q is odd, then return 1 if both (p-q)/2 and (p+q)/2 are squares."

p although not q can be even, so this is flawed; and it doesn't give all the solutions anyway.

Title: Re: Check for Perfect Square
Post by River_Phoenix on May 26^th, 2005, 10:49am

I made a small typo above, so i'll just rewrite:

If q is even, then write q=2n, so 4n^2-p^2=a^2 for some a.
a^2 + p^2 = 4n^2

Since a^2 + p^2 is divisible by 4, a and p are clearly both even or both odd. In fact, they must be both even since (2i+1)^2=4i^2+4i+1 = 1 (mod 4), where (2i+1) represents any odd number; thus a^2+p^2 = 2 (mod 4) when a and p are both odd.

So we have shown that a and p are both even, but q was already even, so p and q are both divisible by 2, which contradicts our assumption that p and q are written so as to be relatively prime.

Title: Re: Check for Perfect Square
Post by towr on May 26^th, 2005, 12:43pm

Quote:

which contradicts our assumption that p and q are written so as to be relatively prime.

And what if the assumption is wrong?
The opening post says nothing about p and q being relatively prime. Reducing them to relatively prime numbers makes sense though..

Besides which you skipped the line above it, handling the p=even case.

Title: Re: Check for Perfect Square
Post by River_Phoenix on May 26^th, 2005, 3:04pm

p and q can be written as relatively prime WLOG, as you say. And I've only solved the case where q (the hypotenuse of the pythagorean triple) is even - it is impossible in the relatively prime case. I still don't know about q being odd, since the argument made above isn't really correct.

In other words, if you have p and q, first make them relatively prime; then we have that q* is not even.

Title: Re: Check for Perfect Square
Post by towr on May 27^th, 2005, 12:05am

If you take q to be the hypothenuse, then you're making the opposite assumption others have made in the thread, which is p > q. You can assume either WLOG, naturally, but it's important to note which you choose.
In a pythagorean triple there is one even and two odd sides. And the hypothenuse is always odd. So if we have relatively prime p and q, and the hypothenuse (the larger of the two numbers) is even, then there can be no solution.
So we still have to look at the case where the hypothenuse is odd, and the subcases 1) the other side is odd, 2) the other side is even

In case 1),
(p-q)/2 , (p+q)/2 and 4 must all be factors of p² - q²
Furthermore (p-q)/2 and (p+q)/2 must still be coprime, and therefor must both be squares if p² - q² is to be square.
So as Barukh said, in this case it suffices to check (p-q)/2 , (p+q)/2

But that still leaves case 2)
( you can look at (p-q) and (p+q), but the latter may give an integer overflow )

Title: Re: Check for Perfect Square
Post by River_Phoenix on May 27^th, 2005, 5:58am

I see; I mixed up p and q. I have no idea about the case where their both even; maybe there's some kind of reduction algorithm.

Title: Re: Check for Perfect Square
Post by rene on May 30^th, 2005, 5:48am

can you guys suggest the best waY to find if the number is a perfect square ?????????????/

Title: Re: Check for Perfect Square
Post by towr on May 30^th, 2005, 7:15am

I usually use something along the lines of

is_square(x) := x == floor(sqrt(x))²