flat assembler
Message board for the users of flat assembler.
 Home   FAQ   Search   Register 
 Profile   Log in to check your private messages   Log in 
flat assembler > Main > quickest way to check if a number is a square

Goto page 1, 2, 3, 4  Next
Author
Thread Post new topic Reply to topic
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 Wink
Post 28 Aug 2011, 20:59
View user's profile Send private message Reply with quote
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)
Post 28 Aug 2011, 22:18
View user's profile Send private message Reply with quote
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 Smile

Many thanks Very Happy

magic²
Post 28 Aug 2011, 22:51
View user's profile Send private message Reply with quote
Madis731



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.
Post 29 Aug 2011, 06:24
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
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 Razz
Post 29 Aug 2011, 07:49
View user's profile Send private message Reply with quote
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?
Post 29 Aug 2011, 08:00
View user's profile Send private message Visit poster's website Reply with quote
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 == 1or (n & 31 == 4or (n & 127 == 16or (n & 191 == 0then
    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 Razz

_________________
Nil Volentibus Arduum Razz
Post 29 Aug 2011, 08:12
View user's profile Send private message Reply with quote
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".
Post 29 Aug 2011, 08:33
View user's profile Send private message Visit poster's website Reply with quote
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





Razz Razz Razz Razz Razz Razz

_________________
Nil Volentibus Arduum Razz
Post 29 Aug 2011, 08:51
View user's profile Send private message Reply with quote
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²
Post 29 Aug 2011, 11:04
View user's profile Send private message Reply with quote
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 Wink

_________________
Nil Volentibus Arduum Razz
Post 29 Aug 2011, 11:35
View user's profile Send private message Reply with quote
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 Razz
Post 29 Aug 2011, 12:23
View user's profile Send private message Reply with quote
magicSqr



Joined: 27 Aug 2011
Posts: 105

Many thanks DJ Very Happy

I'll get a proper look at it after

magic²
Post 29 Aug 2011, 14:18
View user's profile Send private message Reply with quote
magicSqr



Joined: 27 Aug 2011
Posts: 105

Sorry DJ,

Your code misses a lot of squares Sad

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

magic²
Post 29 Aug 2011, 16:25
View user's profile Send private message Reply with quote
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     edxedx                ; first number 0
        mov     ecx100                ; check nums 0 - 100
    .checkSqr:
        mov     eaxedx
        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     eax0x0F
        or      alal
        je      .couldBeSqr
        cmp     al1
        je      .couldBeSqr
        cmp     al4
        je      .couldBeSqr
        cmp     al9
        je      .couldBeSqr
        xor     eaxeax
        ret
    .couldBeSqr:
        mov     eax1
        ret
endp




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

magic²
Post 29 Aug 2011, 16:45
View user's profile Send private message Reply with quote
DJ Mauretto



Joined: 14 Mar 2007
Posts: 464
Location: Rome,Italy

yes, you are right the code is bug Laughing

I do not even know what I wrote Laughing Laughing Laughing Laughing

OK I hope that you have solved the problem Wink

_________________
Nil Volentibus Arduum Razz
Post 29 Aug 2011, 17:01
View user's profile Send private message Reply with quote
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 Razz
Post 29 Aug 2011, 17:46
View user's profile Send private message Reply with quote
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²
Post 29 Aug 2011, 19:53
View user's profile Send private message Reply with quote
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 Wink

_________________
Nil Volentibus Arduum Razz
Post 30 Aug 2011, 05:55
View user's profile Send private message Reply with quote
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 







Embarassed Sorry DJ, I missed that Embarassed

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²
Post 30 Aug 2011, 12:27
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page 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


Powered by phpBB © 2001-2005 phpBB Group.

Main index   Download   Documentation   Examples   Message board
Copyright © 2004-2017, Tomasz Grysztar.