Author |
Topic: Check for Perfect Square (Read 2063 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Check for Perfect Square
« on: Mar 11th, 2005, 3:30am » |
 Quote  Modify
|
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
|
| « Last Edit: Mar 11th, 2005, 3:33am by Barukh » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Check for Perfect Square
« Reply #1 on: Mar 11th, 2005, 4:39am » |
Quote Modify
|
Can I assume that (say p > q) a*p for small a does fit in a word?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Check for Perfect Square
« Reply #2 on: Mar 11th, 2005, 7:30am » |
Quote Modify
|
on Mar 11th, 2005, 4:39am, 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. 
|
|
IP Logged |
|
|
|
VincentLascaux
Guest
|
|
Re: Check for Perfect Square
« Reply #3 on: Mar 11th, 2005, 9:33am » |
Quote Modify
 Remove
|
Can we assume that the sum and difference of p and q fits in a word ?
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);
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Check for Perfect Square
« Reply #4 on: Mar 11th, 2005, 9:49am » |
Quote Modify
|
on Mar 11th, 2005, 9:33am, 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..)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
VincentLascaux
Guest
|
|
Re: Check for Perfect Square
« Reply #5 on: Mar 11th, 2005, 11:43am » |
Quote Modify
Remove
|
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).
|
|
IP Logged |
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
    
Gender:
Posts: 767
|
|
Re: Check for Perfect Square
« Reply #6 on: Mar 11th, 2005, 1:08pm » |
Quote Modify
|
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.
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Check for Perfect Square
« Reply #7 on: Mar 11th, 2005, 2:52pm » |
Quote Modify
|
Bah. Just do a Pythagorean triples lookup.
|
| « Last Edit: Mar 11th, 2005, 2:54pm by Leo Broukhis » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Check for Perfect Square
« Reply #8 on: Mar 11th, 2005, 11:54pm » |
Quote Modify
|
Well done, Vincent! So, what about co-prime p, q (a = 1)?
on Mar 11th, 2005, 2:52pm, Leonid Broukhis wrote:| Bah. Just do a Pythagorean triples lookup. |
|
Interesting idea... But it's not very space-efficient, don't you think? 
|
|
IP Logged |
|
|
|
VincentLascaux
Guest
|
|
Re: Check for Perfect Square
« Reply #9 on: Mar 12th, 2005, 3:44am » |
Quote Modify
Remove
|
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)
|
|
IP Logged |
|
|
|
VincentLascaux
Guest
|
|
Re: Check for Perfect Square
« Reply #10 on: Mar 12th, 2005, 3:51am » |
Quote Modify
Remove
|
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...
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Check for Perfect Square
« Reply #11 on: Mar 12th, 2005, 5:36am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
gniv
Newbie
Gender:
Posts: 19
|
|
Re: Check for Perfect Square
« Reply #12 on: Mar 12th, 2005, 6:02am » |
Quote Modify
|
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.
|
| « Last Edit: Mar 12th, 2005, 8:07am by gniv » |
IP Logged |
|
|
|
VincentLascaux
Guest
|
|
Re: Check for Perfect Square
« Reply #13 on: Mar 12th, 2005, 6:23am » |
Quote Modify
Remove
|
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?
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Check for Perfect Square
« Reply #14 on: Mar 12th, 2005, 7:20am » |
Quote Modify
|
on Mar 12th, 2005, 6:23am, 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... 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Check for Perfect Square
« Reply #15 on: Mar 12th, 2005, 1:13pm » |
Quote Modify
|
on Mar 12th, 2005, 7:20am, 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)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Check for Perfect Square
« Reply #16 on: Mar 13th, 2005, 2:42am » |
Quote Modify
|
on Mar 12th, 2005, 1:13pm, towr wrote:
If p>q, I can see why, but as you haven't stated that's the case: p=4, q=5 |
|
Towr, I tacitly used your assumption from this post:
on Mar 11th, 2005, 4:39am, towr wrote:| Can I assume that (say p > q) a*p for small a does fit in a word? |
|
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Check for Perfect Square
« Reply #17 on: Mar 13th, 2005, 8:14am » |
Quote Modify
|
on Mar 12th, 2005, 7:20am, 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..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
River Phoenix
Guest
|
|
Re: Check for Perfect Square
« Reply #18 on: May 26th, 2005, 10:28am » |
Quote Modify
Remove
|
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.
|
|
IP Logged |
|
|
|
River Phoenix
Junior Member
Gender:
Posts: 125
|
|
Re: Check for Perfect Square
« Reply #19 on: May 26th, 2005, 10:35am » |
Quote Modify
|
"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.
|
|
IP Logged |
|
|
|
River Phoenix
Junior Member
Gender:
Posts: 125
|
|
Re: Check for Perfect Square
« Reply #20 on: May 26th, 2005, 10:49am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Check for Perfect Square
« Reply #21 on: May 26th, 2005, 12:43pm » |
Quote Modify
|
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.
|
| « Last Edit: May 26th, 2005, 12:45pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
River Phoenix
Junior Member
Gender:
Posts: 125
|
|
Re: Check for Perfect Square
« Reply #22 on: May 26th, 2005, 3:04pm » |
Quote Modify
|
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.
|
| « Last Edit: May 26th, 2005, 3:05pm by River Phoenix » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Check for Perfect Square
« Reply #23 on: May 27th, 2005, 12:05am » |
Quote Modify
|
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 p2 - q2
Furthermore (p-q)/2 and (p+q)/2 must still be coprime, and therefor must both be squares if p2 - q2 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 )
|
| « Last Edit: May 27th, 2005, 12:12am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
River Phoenix
Junior Member
Gender:
Posts: 125
|
|
Re: Check for Perfect Square
« Reply #24 on: May 27th, 2005, 5:58am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print