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
Thread Post new topic Reply to topic
Goplat



Joined: 15 Sep 2006
Posts: 181
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?
Post 30 Aug 2011, 15:14
View user's profile Send private message Reply with quote
magicSqr



Joined: 27 Aug 2011
Posts: 105
magicSqr
Hi Goplat,

If you check back to the OP, you'll see it started with me asking if using the FPU was the quickest way of checking if a number was square. It turns out it isn't as the FPU is slower than the CPU.

What DJ's algo does is weed out a lot of numbers that aren't square, so only the remaining ones need to be run through the FPU for a definitive check.

For the numbers 0 to 1000, the algo dismisses 827 of them, leaving only 173 to be put through the FPU Very Happy

magic²


Last edited by magicSqr on 30 Aug 2011, 19:41; edited 1 time in total
Post 30 Aug 2011, 15:36
View user's profile Send private message Reply with quote
DJ Mauretto



Joined: 14 Mar 2007
Posts: 464
Location: Rome,Italy
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 Wink

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 Razz

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 Razz Razz Razz

Let you to write a decent algo Rolling Eyes

_________________
Nil Volentibus Arduum Razz
Post 30 Aug 2011, 17:37
View user's profile Send private message Reply with quote
magicSqr



Joined: 27 Aug 2011
Posts: 105
magicSqr
Hi DJ,

For a quickly thrown together code it's actually not bad Very Happy

It cuts processing time by approx 33% Wink

magic²
Post 30 Aug 2011, 18:57
View user's profile Send private message Reply with quote
DJ Mauretto



Joined: 14 Mar 2007
Posts: 464
Location: Rome,Italy
DJ Mauretto
Quote:
Hi DJ,

For a quickly thrown together code it's actually not bad

It cuts processing time by approx 33%


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 '.
Rolling Eyes Rolling Eyes Rolling Eyes

_________________
Nil Volentibus Arduum Razz
Post 31 Aug 2011, 06:03
View user's profile Send private message Reply with quote
ouadji



Joined: 24 Dec 2008
Posts: 1081
Location: Belgium
ouadji
Quote:
@DJ Mauretto

200h = 512 , it ends with zero preceded by another zero
then it should be a perfect square but it is not '.
Quote:
@Wiki

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,

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. Wink

_________________
I am not young enough to know everything (Oscar Wilde)- Image
Post 31 Aug 2011, 07:33
View user's profile Send private message Send e-mail Reply with quote
DJ Mauretto



Joined: 14 Mar 2007
Posts: 464
Location: Rome,Italy
DJ Mauretto
Quote:

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.


I don't understand Rolling Eyes
Anyway i'm happy for you if you understand it Wink

_________________
Nil Volentibus Arduum Razz
Post 31 Aug 2011, 08:08
View user's profile Send private message Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4242
Location: 2018
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!! Laughing
Post 31 Aug 2011, 10:06
View user's profile Send private message Visit poster's website Reply with quote
ouadji



Joined: 24 Dec 2008
Posts: 1081
Location: Belgium
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)- Image
Post 31 Aug 2011, 10:37
View user's profile Send private message Send e-mail Reply with quote
DJ Mauretto



Joined: 14 Mar 2007
Posts: 464
Location: Rome,Italy
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 Razz
Post 31 Aug 2011, 12:29
View user's profile Send private message Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2140
Location: Estonia
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.
Post 31 Aug 2011, 15:08
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
magicSqr



Joined: 27 Aug 2011
Posts: 105
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 Very Happy
Post 31 Aug 2011, 16:48
View user's profile Send private message Reply with quote
DJ Mauretto



Joined: 14 Mar 2007
Posts: 464
Location: Rome,Italy
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 Wink

The algo on wiki is crap Razz

_________________
Nil Volentibus Arduum Razz
Post 31 Aug 2011, 17:09
View user's profile Send private message Reply with quote
ouadji



Joined: 24 Dec 2008
Posts: 1081
Location: Belgium
ouadji
Quote:
@DJ Mauretto
Where it is written 'Can be a perfect square ... and not ... is a perfect square ?

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)- Image
Post 31 Aug 2011, 19:47
View user's profile Send private message Send e-mail Reply with quote
r22



Joined: 27 Dec 2004
Posts: 805
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
Post 31 Aug 2011, 19:52
View user's profile Send private message AIM Address Yahoo Messenger Reply with quote
magicSqr



Joined: 27 Aug 2011
Posts: 105
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 Very Happy

magic²
Post 31 Aug 2011, 19:59
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17665
Location: In your JS exploiting you and your system
revolution
r22 wrote:
6 instructions
Merely counting instructions is not a way to predict the speed of execution. The SSE SQRT is just as slow as the FPU SQRT, both will use the same internal circuitry to do the computation.
Post 31 Aug 2011, 20:19
View user's profile Send private message Visit poster's website Reply with quote
magicSqr



Joined: 27 Aug 2011
Posts: 105
magicSqr
OK, thanks for that revolution Wink
Post 31 Aug 2011, 20:23
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17665
Location: In your JS exploiting you and your system
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.
Looks to be easy to prove.

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).
Post 31 Aug 2011, 20:46
View user's profile Send private message Visit poster's website Reply with quote
magicSqr



Joined: 27 Aug 2011
Posts: 105
magicSqr
ya must've missed my

N = u²

post then Very Happy
Post 31 Aug 2011, 20:51
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page Previous  1, 2, 3, 4  Next

< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on GitHub, YouTube, Twitter.

Website powered by rwasa.