flat assembler
Message board for the users of flat assembler.
![]() Goto page Previous 1, 2, 3, 4 Next |
Author |
|
Goplat 30 Aug 2011, 15:14
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?
|
|||
![]() |
|
DJ Mauretto 30 Aug 2011, 17:37
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 ![]() |
|||
![]() |
|
magicSqr 30 Aug 2011, 18:57
Hi DJ,
For a quickly thrown together code it's actually not bad ![]() It cuts processing time by approx 33% ![]() magic² |
|||
![]() |
|
DJ Mauretto 31 Aug 2011, 06:03
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 ![]() |
|||
![]() |
|
ouadji 31 Aug 2011, 07:33
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. ![]() |
|||
![]() |
|
DJ Mauretto 31 Aug 2011, 08:08
Quote:
I don't understand ![]() Anyway i'm happy for you if you understand it ![]() _________________ Nil Volentibus Arduum ![]() |
|||
![]() |
|
edfed 31 Aug 2011, 10:06
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!! ![]() |
|||
![]() |
|
ouadji 31 Aug 2011, 10:37
@DJ Mauretto I just thought that it could be a distraction. This can happen ... i was just surprised by your answer, nothing else. |
|||
![]() |
|
DJ Mauretto 31 Aug 2011, 12:29
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 ![]() |
|||
![]() |
|
Madis731 31 Aug 2011, 15:08
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. |
|||
![]() |
|
magicSqr 31 Aug 2011, 16:48
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 ![]() |
|||
![]() |
|
DJ Mauretto 31 Aug 2011, 17:09
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 ![]() |
|||
![]() |
|
ouadji 31 Aug 2011, 19:47
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. |
|||
![]() |
|
r22 31 Aug 2011, 19:52
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 |
|||
![]() |
|
magicSqr 31 Aug 2011, 19:59
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² |
|||
![]() |
|
revolution 31 Aug 2011, 20:19
r22 wrote: 6 instructions |
|||
![]() |
|
magicSqr 31 Aug 2011, 20:23
OK, thanks for that revolution
![]() |
|||
![]() |
|
revolution 31 Aug 2011, 20:46
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). |
|||
![]() |
|
magicSqr 31 Aug 2011, 20:51
ya must've missed my
N = u² post then ![]() |
|||
![]() |
|
Goto page Previous 1, 2, 3, 4 Next < Last Thread | Next Thread > |
Forum Rules:
|
Copyright © 1999-2025, Tomasz Grysztar. Also on GitHub, YouTube.
Website powered by rwasa.