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

Joined: 15 Sep 2006
Posts: 181
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?
30 Aug 2011, 15:14
magicSqr

Joined: 27 Aug 2011
Posts: 105
magicSqr 30 Aug 2011, 15:36
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

magic²

Last edited by magicSqr on 30 Aug 2011, 19:41; edited 1 time in total
30 Aug 2011, 15:36
DJ Mauretto

Joined: 14 Mar 2007
Posts: 464
Location: Rome,Italy
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
30 Aug 2011, 17:37
magicSqr

Joined: 27 Aug 2011
Posts: 105
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²
30 Aug 2011, 18:57
DJ Mauretto

Joined: 14 Mar 2007
Posts: 464
Location: Rome,Italy
DJ Mauretto 31 Aug 2011, 06:03
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 '.

_________________
Nil Volentibus Arduum
31 Aug 2011, 06:03

Joined: 24 Dec 2008
Posts: 1081
Location: Belgium
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.

_________________
I am not young enough to know everything (Oscar Wilde)-
31 Aug 2011, 07:33
DJ Mauretto

Joined: 14 Mar 2007
Posts: 464
Location: Rome,Italy
DJ Mauretto 31 Aug 2011, 08:08
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
Anyway i'm happy for you if you understand it

_________________
Nil Volentibus Arduum
31 Aug 2011, 08:08
edfed

Joined: 20 Feb 2006
Posts: 4283
Location: Now
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!!
31 Aug 2011, 10:06

Joined: 24 Dec 2008
Posts: 1081
Location: Belgium

@DJ Mauretto

I just thought that it could be a distraction. This can happen ...

_________________
I am not young enough to know everything (Oscar Wilde)-
31 Aug 2011, 10:37
DJ Mauretto

Joined: 14 Mar 2007
Posts: 464
Location: Rome,Italy
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
31 Aug 2011, 12:29

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia
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

Joined: 27 Aug 2011
Posts: 105
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
31 Aug 2011, 16:48
DJ Mauretto

Joined: 14 Mar 2007
Posts: 464
Location: Rome,Italy
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
31 Aug 2011, 17:09

Joined: 24 Dec 2008
Posts: 1081
Location: Belgium
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)-
31 Aug 2011, 19:47
r22

Joined: 27 Dec 2004
Posts: 805
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
31 Aug 2011, 19:52
magicSqr

Joined: 27 Aug 2011
Posts: 105
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²
31 Aug 2011, 19:59
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 19096
revolution 31 Aug 2011, 20:19
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.
31 Aug 2011, 20:19
magicSqr

Joined: 27 Aug 2011
Posts: 105
magicSqr 31 Aug 2011, 20:23
OK, thanks for that revolution
31 Aug 2011, 20:23
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 19096
revolution 31 Aug 2011, 20:46
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).
31 Aug 2011, 20:46
magicSqr

Joined: 27 Aug 2011
Posts: 105
magicSqr 31 Aug 2011, 20:51
ya must've missed my

N = u²

post then
31 Aug 2011, 20:51
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area
Goto page Previous  1, 2, 3, 4  Next

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum