flat assembler
Message board for the users of flat assembler.

 Index > Main > quickest way to check if a number is a square Goto page 1, 2, 3, 4  Next
Author
magicSqr

Joined: 27 Aug 2011
Posts: 105
magicSqr 28 Aug 2011, 20:59
Hi,

I want to find out if x is an integer squared. Not being able to find a FP fsqr, is this the quickest method?

Code:
```dd   x 179775

push    [x]
fild    dword [esp]
fsqrt
fistp   dword [esp]
fild    dword [esp]
fimul   dword [esp]
fistp   dword [esp]
pop     esi
cmp     esi, [x]
```

Thanks for any help you can give
28 Aug 2011, 20:59
cod3b453

Joined: 25 Aug 2004
Posts: 618
cod3b453 28 Aug 2011, 22:18
You can use fmul st0,st0 to achieve the squaring:
Code:
```        fild dword [x]  ; st0 = k²
fsqrt           ; st0 = k
frndint         ; st0 = round(k)
fmul st0,st0    ; st0 = round(k)²
ficomp dword [x]; C3 := round(k)² = k²
fstsw ax
sahf            ; C3 -> ZF
jnz .not_square      ```
I don't know how much difference there is between either version in terms of execution speed though. (It will vary between architectures)
28 Aug 2011, 22:18
magicSqr

Joined: 27 Aug 2011
Posts: 105
magicSqr 28 Aug 2011, 22:51
Nice cod3b453,

Quote:

frndint ; st0 = round(k)

I'm very new to FP because I could never get anything to work with it, lol
I didn't know about frndint

Must try a bit of benchmarking to see which is faster, this is for a personal project, so whatever my architecture says

Many thanks

magic²
28 Aug 2011, 22:51

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia
Madis731 29 Aug 2011, 06:24
With the help of Wikipedia. I conclude that you can easily throw out all non-squares, but in the end you still have to test if it fails the tests. Its a probabilistic approach.
http://en.wikipedia.org/wiki/Square_number
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.

179775 failed it so it is definitely non-square.
179776 passed so to be sure, one needs to take square root.
29 Aug 2011, 06:24
DJ Mauretto

Joined: 14 Mar 2007
Posts: 464
Location: Rome,Italy
DJ Mauretto 29 Aug 2011, 07:49
From Wikipedia:

Code:
```
x DD 179775

MOV     EAX,[X]
MOV     EBX,EAX
AND     EBX,7
CMP     EBX,1
JZ      @Is_Square

MOV     EBX,EAX
AND     EBX,31
CMP     EBX,4
JZ      @Is_Square

MOV     EBX,EAX
AND     EBX,127
CMP     EBX,16
JZ      @Is_Square

AND     EAX,191
TEST    EAX,EAX
JZ      @Is_Square

@Not_Square:

DO SOMETHING

@Is_Square:

DO SOMETHING

```

_________________
Nil Volentibus Arduum
29 Aug 2011, 07:49
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 19098
Location: In your JS exploiting you and your system
revolution 29 Aug 2011, 08:00
DJ Mauretto wrote:
From Wikipedia:

Code:
```
x DD 179775

MOV     EAX,[X]
MOV     EBX,EAX
AND     EBX,7
CMP     EBX,1
JZ      @Is_Square

MOV     EBX,EAX
AND     EBX,31
CMP     EBX,4
JZ      @Is_Square

MOV     EBX,EAX
AND     EBX,127
CMP     EBX,16
JZ      @Is_Square

AND     EAX,191
TEST    EAX,EAX
JZ      @Is_Square

@Not_Square:

DO SOMETHING

@Is_Square:

DO SOMETHING

```
Fails for "x DD 17" (and lots of other values). Perhaps you need to check your algorithm for errors?
29 Aug 2011, 08:00
DJ Mauretto

Joined: 14 Mar 2007
Posts: 464
Location: Rome,Italy
DJ Mauretto 29 Aug 2011, 08:12
Quote:
Fails for "x DD 17" (and lots of other values). Perhaps you need to check your algorithm for errors?

Yes, i take from wiki, this is the source:
Code:
```if (n & 7 == 1) or (n & 31 == 4) or (n & 127 == 16) or (n & 191 == 0) then
return n is probably square
else
return n is definitely not square    ```

I haven't check this algorithm, perhaps we need to add something else

_________________
Nil Volentibus Arduum
29 Aug 2011, 08:12
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 19098
Location: In your JS exploiting you and your system
revolution 29 Aug 2011, 08:33
Your label "@Is_Square" is misleading. Perhaps a better name it in order, "@It_might_be_a_square_check_further_to_make_sure".
29 Aug 2011, 08:33
DJ Mauretto

Joined: 14 Mar 2007
Posts: 464
Location: Rome,Italy
DJ Mauretto 29 Aug 2011, 08:51
Code:
```x       DD 179775

MOV     EAX,[X]
MOV     EBX,EAX
AND     EBX,7
CMP     EBX,1
JZ      @It_might_be_a_square_check_further_to_make_sure

MOV     EBX,EAX
AND     EBX,31
CMP     EBX,4
JZ      @It_might_be_a_square_check_further_to_make_sure

MOV     EBX,EAX
AND     EBX,127
CMP     EBX,16
JZ      @It_might_be_a_square_check_further_to_make_sure

AND     EAX,191
TEST    EAX,EAX
JZ      @It_might_be_a_square_check_further_to_make_sure

@Not_Square:

DO SOMETHING

@It_might_be_a_square_check_further_to_make_sure:

DO SOMETHING

```

_________________
Nil Volentibus Arduum
29 Aug 2011, 08:51
magicSqr

Joined: 27 Aug 2011
Posts: 105
magicSqr 29 Aug 2011, 11:04
Code:
```DJ Mauretto wrote:

x       DD 179775

MOV     EAX,[X]
MOV     EBX,EAX
AND     EBX,7
CMP     EBX,1
JZ      @It_might_be_a_square_check_further_to_make_sure

etc

@It_might_be_a_square_check_further_to_make_sure:
```

So with at least 5 instructions to tell me that hmmm maybe it is, maybe it isn't (shhh it's a secret), lol, and 16 instructions to say nope, not sqr it should be quicker to just check if it is or not. Or is it the case that the FPU is slower enough than the CPU to make this worth it¿

magic²
29 Aug 2011, 11:04
DJ Mauretto

Joined: 14 Mar 2007
Posts: 464
Location: Rome,Italy
DJ Mauretto 29 Aug 2011, 11:35
Quote:
So with at least 5 instructions to tell me that hmmm maybe it is, maybe it isn't (shhh it's a secret), lol, and 16 instructions to say nope, not sqr it should be quicker to just check if it is or not. Or is it the case that the FPU is slower enough than the CPU to make this worth it¿

FPU is always more slow, anyway this algorithm is not complete,
i take it from wikipedia, search on google maybe you'll find the complete
algorithm

_________________
Nil Volentibus Arduum
29 Aug 2011, 11:35
DJ Mauretto

Joined: 14 Mar 2007
Posts: 464
Location: Rome,Italy
DJ Mauretto 29 Aug 2011, 12:23
Ok i have a little bit of time to try to write a piece of code:
Try this:

Code:
```
Number       DD 1024

mov     eax,[Number]
call    @Perfect_Square
test    eax,eax                 ; Eax = 0 is not a square, Eax = 1 is  a square

@Perfect_Square:

and     eax,0ffh
mov     bl,al
and     bl,0f0h
shr     bl,1
aaa
test     al,al
jz      @Is_Zero
cmp     al,1
jz      @Is_Square
cmp     al,4
jz      @Is_Four
cmp     al,9
jz      @Is_Square

xor     eax,eax          ; eax = 0 is not a square
ret

@Is_Zero:

xchg    al,ah
aaa
test     al,al
jz      @Is_Square
cmp     al,1
jz      @Is_Square
cmp     al,4
jz      @Is_Square
cmp     al,9
jz      @Is_Square

xor     eax,eax          ; eax = 0 is not a square
ret

@Is_Four:

xchg    al,ah
aaa
test    al,1
jz      @Is_Square

xor     eax,eax          ; eax = 0 is not a square
ret

@Is_Square:

mov     eax,1           ; eax = 1 is a square
ret
```

_________________
Nil Volentibus Arduum
29 Aug 2011, 12:23
magicSqr

Joined: 27 Aug 2011
Posts: 105
magicSqr 29 Aug 2011, 14:18
Many thanks DJ

I'll get a proper look at it after

magic²
29 Aug 2011, 14:18
magicSqr

Joined: 27 Aug 2011
Posts: 105
magicSqr 29 Aug 2011, 16:25
Sorry DJ,

Your code misses a lot of squares

in a loop from 0 to 100 it misses 16, 25, 49 and 81

magic²
29 Aug 2011, 16:25
magicSqr

Joined: 27 Aug 2011
Posts: 105
magicSqr 29 Aug 2011, 16:45
Hi DJ

Just noticed on the wiki that it is base 16 where they all end with 0, 1, 4 or 9

Here's a working algo

Code:
```
xor     edx, edx                ; first number 0
mov     ecx, 100                ; check nums 0 - 100
.checkSqr:
mov     eax, edx
stdcall Perfect_Square
test    eax,eax                 ; Eax = 0 is not a square
jz      @f
;edx here could be a square

@@:
inc     edx
loop    .checkSqr

proc Perfect_Square

and     eax, 0x0F
or      al, al
je      .couldBeSqr
cmp     al, 1
je      .couldBeSqr
cmp     al, 4
je      .couldBeSqr
cmp     al, 9
je      .couldBeSqr
xor     eax, eax
ret
.couldBeSqr:
mov     eax, 1
ret
endp
```

Thanks Madis731 for pointing out the wiki and DJ for putting in the time

magic²
29 Aug 2011, 16:45
DJ Mauretto

Joined: 14 Mar 2007
Posts: 464
Location: Rome,Italy
DJ Mauretto 29 Aug 2011, 17:01
yes, you are right the code is bug

I do not even know what I wrote

OK I hope that you have solved the problem

_________________
Nil Volentibus Arduum
29 Aug 2011, 17:01
DJ Mauretto

Joined: 14 Mar 2007
Posts: 464
Location: Rome,Italy
DJ Mauretto 29 Aug 2011, 17:46
Try this code:

Code:
```
Number  DD 900

mov     eax,[Number]
call    @Perfect_Square
test    eax,eax                 ; Eax = 0 is not a square, Eax = 1 is  a square

ret

@Perfect_Square:

and     eax,0ffh
mov     bl,al
and     al,0fh
test    al,al
jz      @Is_Zero
cmp     al,1
jz      @Is_Square
cmp     al,4
jz      @Is_Four
cmp     al,9
jz      @Is_Square

xor     eax,eax          ; eax = 0 is not a square
ret

@Is_Zero:

mov     al,bl
shr     al,4
test    al,al
jz      @Is_Square
cmp     al,1
jz      @Is_Square
cmp     al,4
jz      @Is_Square
cmp     al,9
jz      @Is_Square

xor     eax,eax          ; eax = 0 is not a square
ret

@Is_Four:

mov     al,bl
shr     al,4
test    al,1
jz      @Is_Square

xor     eax,eax          ; eax = 0 is not a square
ret

@Is_Square:

mov     eax,1           ; eax = 1 is a square
ret

```

_________________
Nil Volentibus Arduum
29 Aug 2011, 17:46
magicSqr

Joined: 27 Aug 2011
Posts: 105
magicSqr 29 Aug 2011, 19:53
Hi DJ,

Your main mistake is

Code:
```and     eax,0ffh
```

you need this to be

Code:
```and     eax,0fh
```

The reason is this

144d (12²) = 90h (you are testing if 90 = 0, 1, 4, 9)
15129d (123²) = 3B19h (you are testing if 19 = 0, 1, 4, 9)

where wiki states:

Quote:

There is a simple Boolean formula to perform this test on any number n using only the least significant byte

it is in fact wrong. It should be the least significant nibble.

So we 'AND' everything else out and just test if this nibble is 0, 1, 4 or 9

magic²
29 Aug 2011, 19:53
DJ Mauretto

Joined: 14 Mar 2007
Posts: 464
Location: Rome,Italy
DJ Mauretto 30 Aug 2011, 05:55
NO..
Read better the code..
Code:
```        and     eax,0ffh
mov     bl,al
and     al,0fh
```

I save last byte then test the nibble..
If this niblle is 0 or 4 then i check for the nibble that precede it...
Please try the last code that i wrote

_________________
Nil Volentibus Arduum
30 Aug 2011, 05:55
magicSqr

Joined: 27 Aug 2011
Posts: 105
magicSqr 30 Aug 2011, 12:27
DJ Mauretto wrote:
NO..
Read better the code..
Code:
```        and     eax,0ffh
mov     bl,al
and     al,0fh
```

Sorry DJ, I missed that

I like the 2nd tests for isZero and isFour, I hadn't thought of checking if the 2nd nibble was useful.

Very nice.

Thank you,

magic²
30 Aug 2011, 12:27
 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 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