quickest way to check if a number is a square

Index > Main > quickest way to check if a number is a square

Goto page 1, 2, 3, 4 Next

Author

Thread

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 Wink

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 Smile

Many thanks Very Happy

magic²

28 Aug 2011, 22:51

Madis731

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 Razz

29 Aug 2011, 07:49

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20337
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 Razz

_________________
Nil Volentibus Arduum Razz

29 Aug 2011, 08:12

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20337
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 Razz

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 Wink

_________________
Nil Volentibus Arduum Razz

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

29 Aug 2011, 12:23

magicSqr

Joined: 27 Aug 2011
Posts: 105

magicSqr 29 Aug 2011, 14:18

Many thanks DJ Very Happy

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 Sad

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 Very Happy

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 Laughing

I do not even know what I wrote Laughing

OK I hope that you have solved the problem Wink

_________________
Nil Volentibus Arduum Razz

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 Razz

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 Wink

_________________
Nil Volentibus Arduum Razz

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

30 Aug 2011, 12:27

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