Index
> Main > quickest way to check if a number is a squareGoto page Previous 1, 2, 3, 4 Next |
| Author |
|
|
Goplat
If all you're doing is checking the low 8 bits, how can your function know that 100h is a square and 200h is not?
|
|||
30 Aug 2011, 15:14 |
|
|
DJ Mauretto
Quote: If all you're doing is checking the low 8 bits, how can your function know that 100h is a square and 200h is not? You are right this algo is bad 
Quote: What DJ's algo does is weed out a lot of numbers that aren't square, so only the remaing ones need to be run through the FPU for a definitive check. Note this is not my algo, it is from wikipedia, i don't have check it I'm not interested in the perfect square 
Wiki says: In base 16, a square number can end only with 0,1,4 or 9 and - in case 0, only 0,1,4,9 can precede it, - in case 4, only even numbers can precede it. I wrote this algo , but it's bad
Let you to write a decent algo  _________________ Nil Volentibus Arduum |
|||
|
30 Aug 2011, 17:37 |
|
|
magicSqr
Hi DJ,
For a quickly thrown together code it's actually not bad 
It cuts processing time by approx 33%
magic² |
|||
|
30 Aug 2011, 18:57 |
|
|
DJ Mauretto
Quote: Hi DJ, Certainly, but what wiki says is false, the algo don't work for many numbers, perhaps I did not understand the algo. 200h = 512 , it ends with zero preceded by another zero then it should be a perfect square but it is not '. _________________ Nil Volentibus Arduum |
|||
|
31 Aug 2011, 06:03 |
|
|
ouadji
Quote: @DJ Mauretto Quote: @Wiki my English is very bad, but "wiki" says "in case 0, only 0,1,4,9 CAN precede it". A number that ends with 00 can be a perfect square ... and not ... is a perfect square. It's a possibility, not a certainty. Or maybe my English is even worse than it is.
_________________ I am not young enough to know everything (Oscar Wilde)-  |
|||
|
31 Aug 2011, 07:33 |
|
|
DJ Mauretto
Quote:
I don't understand
Anyway i'm happy for you if you understand it _________________ Nil Volentibus Arduum |
|||
|
31 Aug 2011, 08:08 |
|
|
edfed
Code: mov [x],???? call testsquare cmp eax,1 jne notsquare ... testsquare: if x=(sqrt(x))² then return 1 else return 0 end if asm powaaa!!  |
|||
|
31 Aug 2011, 10:06 |
|
|
ouadji
@DJ Mauretto I just thought that it could be a distraction. This can happen ... i was just surprised by your answer, nothing else. _________________ I am not young enough to know everything (Oscar Wilde)- |
|||
|
31 Aug 2011, 10:37 |
|
|
DJ Mauretto
Quote: A number that ends with 00 can be a perfect square ... and not ... is a perfect square In base 16, a square number can end only with 0,1,4 or 9 and - in case 0, only 0,1,4,9 can precede it, - in case 4, only even numbers can precede it. Where it is written 'Can be a perfect square ... and not ... is a perfect square ? _________________ Nil Volentibus Arduum |
|||
|
31 Aug 2011, 12:29 |
|
|
Madis731
Maybe somebody can prove it, but for every number, N, that is a perfect square, there is a number 2*N, that is not.
Some examples: 1024^.5=32, whereas 2048^.5=45,25... 4294967296^.5=65536, but 8589934592^.5=92681,90... These examples all end in multiple zeroes in base 16. Perfect squares therefore cannot be evaluated in constant time. Lets call it a "theorem". I found out that every time you multiply a perfect square with a prime, you'll effectively make it not perfect... hmm... needs investigation. |
|||
|
31 Aug 2011, 15:08 |
|
|
magicSqr
if N is a perfect square, then there is an integer u such that
N = u² It follows that if 2N is also a square, then 2N = 2u² It's root will be u * sqrt(2) Any integer * sqrt(2) cannot be an integer. QED |
|||
|
31 Aug 2011, 16:48 |
|
|
DJ Mauretto
Quote: Maybe somebody can prove it, but for every number, N, that is a perfect square, there is a number 2*N, that is not. Right man
The algo on wiki is crap _________________ Nil Volentibus Arduum |
|||
|
31 Aug 2011, 17:09 |
|
|
ouadji
Quote: @DJ Mauretto a - In base 16, a square number can end only with 0,1,4 or 9 b - in case 0, only 0,1,4,9 can precede it, c - in case 4, only even numbers can precede it. d - A number that ends with 00 can be a perfect square, and not ... is a perfect square This is written nowhere, it's just a logical deduction a+b => d in other words,in base 16, a number that ends with "00" can be a perfect square ... but, in base 16, all numbers ending with 00 are not necessarily perfect squares. _________________ I am not young enough to know everything (Oscar Wilde)- |
|||
|
31 Aug 2011, 19:47 |
|
|
r22
This is silly. The quickest way is to use SSE
- Convert integer to double FP CVTSI2SD - Find the square root SQRTSD - Floor ROUNDSD - Square MULSD - Convert double FP to integer CVTTSD2SI - Compare with original CMP 6 instructions |
|||
|
31 Aug 2011, 19:52 |
|
|
magicSqr
r22
That's what I originally thought. Having tested DJ's unoptimized algo against straight checking wiith FPU, it is actually reduces checking time by about 33%. Not sure about SSE though, I'll have to read up on it
magic² |
|||
|
31 Aug 2011, 19:59 |
|
|
revolution
r22 wrote: 6 instructions |
|||
|
31 Aug 2011, 20:19 |
|
|
magicSqr
OK, thanks for that revolution
|
|||
|
31 Aug 2011, 20:23 |
|
|
revolution
Madis731 wrote: Maybe somebody can prove it, but for every number, N, that is a perfect square, there is a number 2*N, that is not. N (our perfect square) = m * m 2N = 2 * m * m sqrt(2N) = sqrt(2 * m * m) = sqrt(2) * m sqrt(2) is proven irrational so sqrt(2) * m can never be a perfect square no matter what integer you choose for m (disregarding the degenerate case of m=0). |
|||
|
31 Aug 2011, 20:46 |
|
|
magicSqr
ya must've missed my
N = u² post then |
|||
|
31 Aug 2011, 20:51 |
|
| Goto page Previous 1, 2, 3, 4 Next < Last Thread | Next Thread > |
Forum Rules:
|