flat assembler
Message board for the users of flat assembler.
Index
> Main > quickest way to check if a number is a square Goto 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. 

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. 

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. 

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:

Copyright © 19992020, Tomasz Grysztar. Also on GitHub, YouTube, Twitter.
Website powered by rwasa.