flat assembler
Message board for the users of flat assembler.

Index > Windows > Prime Numbers

Author
Thread Post new topic Reply to topic
SolidThink



Joined: 16 Oct 2009
Posts: 23
SolidThink
Hello,
are new ,
i understand the assembler logic structure;

someone makes a routine example
that researches between 2 to 1000 #, only the
prime numbers, so that i see the code and
understand his logic ? Very Happy

Thanks
Post 16 Oct 2009, 14:29
View user's profile Send private message Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2141
Location: Estonia
Madis731
Post 16 Oct 2009, 14:54
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
SolidThink



Joined: 16 Oct 2009
Posts: 23
SolidThink
Madis731 wrote:
http://board.flatassembler.net/topic.php?t=7153



big thanks Smile
Post 16 Oct 2009, 16:08
View user's profile Send private message Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
Just for the record, also a naive method: http://board.flatassembler.net/topic.php?p=96788#96788
Post 16 Oct 2009, 17:21
View user's profile Send private message Reply with quote
pal



Joined: 26 Aug 2008
Posts: 227
pal
I implemented Fermat's primality test for numbers in the 32-bit range (will update it to a greater range in the future):

Code:
proc        FermatPrimality,lNum,lIterations
    push    ebp
 mov             ebp,esp
     push    ebx
 push    edi
 xor             eax,eax
     cmp             [lNum],1
    jle             FermatEnd
   cmp             [lIterations],0
     jz              FermatEnd
   mov             ecx,[lIterations]
   
    rdtsc
       push    eax
 call    RandomNumber
        FermatLoop:
             call    ProduceRandom
               xor             edx,edx
             div             [lNum]
              inc             edx
         mov             ebx,edx ; ebx = random number < prime number
             
            mov             eax,1
               mov             edi,[lNum]
          dec             edi
         xymodmLoop: ; Modular exponentiation
                    test    edi,1 ; y odd?
                      jz              @F
                  mul             ebx
                 div             [lNum]
                      mov             eax,edx
             @@: shr             edi,1
                       xchg    eax,ebx
                     mul             eax
                 div             [lNum]
                      mov             eax,edx
                     xchg    ebx,eax
                     test    edi,edi
                     jnz             xymodmLoop
          cmp             eax,1 ; eax = result of above
               jne             @F
          dec             ecx
         test    ecx,ecx
             setz    al
          jz              FermatEnd
           jmp             FermatLoop
  
@@:     xor             eax,eax 
FermatEnd:
  pop             edi
 pop             ebx
 mov             esp,ebp
     pop             ebp
 ret
endp

proc ProduceRandom
       ; u = u * 2862933555777941757LL + 7046029254386353087LL;
    mov             eax,2862933555
      movd    xmm2,eax
    pslldq  xmm2,4
      mov             eax,777941757
       movd    xmm3,eax
    paddd   xmm2,xmm3
   pmuludq xmm0,xmm2
   mov             eax,704602925
       movd    xmm2,eax
    pslldq  xmm2,4
      mov             eax,4000000000
      movd    xmm3,eax
    paddd   xmm2,xmm3
   mov             eax,386353087
       movd    xmm3,eax
    paddd   xmm2,xmm3
   paddq   xmm0,xmm2
   
    ; v ^= v >> 17; v ^= v << 31; v ^= v >> 8
 ; v = xmm7
  movq    xmm6,xmm7
   psrldq  xmm6,17 ; v >> 17
     pxor    xmm7,xmm6 ; v ^= v
  movq    xmm6,xmm7
   pslldq  xmm6,31 ; v << 31
     pxor    xmm7,xmm6 ; v ^= v
  movq    xmm6,xmm7
   psrldq  xmm6,8 ; v >> 8
       pxor    xmm7,xmm6 ; v ^= v
  pxor    xmm6,xmm6
   
    ; w = 4294957665 * (w & 0xFFFFFFFF) + (w >> 32)
   ; w = xmm5
  movq    xmm6,xmm5
   mov             eax,4294957665
      movd    xmm4,eax
    mov             eax,0xFFFFFFFF
      movd    xmm3,eax
    pand    xmm6,xmm3
   pmuludq xmm6,xmm4
   psrldq  xmm5,32
     paddq   xmm5,xmm6
   pxor    xmm3,xmm3 ; Cleanup
 pxor    xmm4,xmm4
   pxor    xmm6,xmm6
   
    ; x = u ^ (u << 21); x ^= x >> 35; x ^= x << 4;
   ; x = xmm6
  movq    xmm6,xmm0
   movq    xmm4,xmm0
   pslldq  xmm4,31 ; x << 31
     pxor    xmm6,xmm4 ; x ^= x
  movq    xmm4,xmm6 
  psrldq  xmm4,35 ; x >> 35
     pxor    xmm6,xmm4 ; x ^= x
  movq    xmm4,xmm6
   pslldq  xmm4,4 ; x << 4
       pxor    xmm6,xmm4 ; x ^= x
  
    ; return (x + v) ^ w;
       movq    xmm4,xmm6 
  paddq   xmm4,xmm7 ; x + v
   pxor    xmm4,xmm5
   movd    eax,xmm4
    ret
endp

proc         RandomNumber,lSeed
  mov             eax,[lSeed]
 movd    xmm0,eax
    mov             eax,4101842887
      movd    xmm7,eax
    pslldq  xmm7,4
      mov             eax,655102017
       movd    xmm2,eax 
   paddd   xmm7,xmm2 
  pxor    xmm0,xmm7 ; u = j ^ v
       call    ProduceRandom
       movq    xmm7,xmm0 ; v = u
   call    ProduceRandom
       movq    xmm5,xmm7 ; w = v
   call    ProduceRandom
       ret
endp
    


The code also has a nice pseudo-random number generator, but it will show you a way of testing for prime numbers (note it is probably sub-optimal and was written a while ago but it is a POC).

Also, I think windwakr implemented Solovay–Strassen I believe, so you may be able to ask him to see what his code looks like.
Post 16 Oct 2009, 17:50
View user's profile Send private message Reply with quote
windwakr



Joined: 30 Jun 2004
Posts: 827
Location: Michigan, USA
windwakr
I think you have me mistaken with someone else. I can't even pronounce that! Razz

I've looked extensively into primality tests, but have never actually done anything.

_________________
----> * <---- My star, won HERE
Post 16 Oct 2009, 18:30
View user's profile Send private message Reply with quote
pal



Joined: 26 Aug 2008
Posts: 227
pal
Ahh Razz I assumed as I remember a thread where we were talking about modular exponentiation (one of asmcoder's awesome threads) and you said that you looked at it a while back for a primality test, so I assume you implemented it.

Edit: Found it:

Code:
http://board.flatassembler.net/topic.php?t=10428&postdays=0&postorder=asc&start=0    


Looks like it was the Miller-Rabin test you were looking at, my mistake. I forgot which one it was.
Post 16 Oct 2009, 19:07
View user's profile Send private message Reply with quote
windwakr



Joined: 30 Jun 2004
Posts: 827
Location: Michigan, USA
windwakr
Ya, I was/am too lazy to do anything. I planned on trying to implement it once, but decided it would be too much work....

_________________
----> * <---- My star, won HERE
Post 16 Oct 2009, 19:14
View user's profile Send private message Reply with quote
pal



Joined: 26 Aug 2008
Posts: 227
pal
Haha. I was deciding on whether or not to implement it, but I decided upon doing Fermat's one as it was easier to do Razz
Post 16 Oct 2009, 19:21
View user's profile Send private message Reply with quote
SolidThink



Joined: 16 Oct 2009
Posts: 23
SolidThink
pal wrote:
Haha. I was deciding on whether or not to implement it, but I decided upon doing Fermat's one as it was easier to do Razz



Please, PAL,
your code shown functions,
but,
i'm not a genius of asm,
please
show me how make
calls to functions with
your remarks,;
your remarks are very very useful

thanks

Smile
Post 17 Oct 2009, 00:38
View user's profile Send private message Reply with quote
pal



Joined: 26 Aug 2008
Posts: 227
pal
Code:
push 5
push       1476425
call         FermatPrimality
    


That will test the number 1476425 for being a prime with a maximum of 5 iterations. The function calls the PRNG itself with the low-dword return from rdtsc as the seed, so you needn't call either of the pseudo-random functions.
Post 17 Oct 2009, 11:41
View user's profile Send private message Reply with quote
SolidThink



Joined: 16 Oct 2009
Posts: 23
SolidThink
pal wrote:
Code:
push 5
push       1476425
call         FermatPrimality
    


That will test the number 1476425 for being a prime with a maximum of 5 iterations. The function calls the PRNG itself with the low-dword return from rdtsc as the seed, so you needn't call either of the pseudo-random functions.


but... for me... now... is very hard , i search a more simple codes
eg. (in basic)

b=0
repeat
a=a+1
if a=prime
b=b+1
endif
if b=100
exit
endif
forever

Smile
Post 17 Oct 2009, 23:10
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< 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


Copyright © 1999-2020, Tomasz Grysztar.

Powered by rwasa.