flat assembler
Message board for the users of flat assembler.
 flat assembler > 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

# quickest way to check if a number is a square

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: 616
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
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: 2146
Location: Estonia
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
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: 15368
Location: 77256 23rd Street

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
 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: 15368
Location: 77256 23rd Street
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
 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
 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
 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
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         add     bl,bl        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
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
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
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
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
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
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
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

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----------------Blog General----------------MainDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsCompiler InternalsIDE DevelopmentOS ConstructionNon-x86 architecturesHigh Level LanguagesProgramming Language DesignProjects and IdeasExamples and Tutorials 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