flat assembler
Message board for the users of flat assembler.

 Index > Windows > Prime Numbers
Author
 Thread
SolidThink

Joined: 16 Oct 2009
Posts: 23
SolidThink 16 Oct 2009, 14:29
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 ?

Thanks
16 Oct 2009, 14:29
Madis731

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia
Madis731 16 Oct 2009, 14:54
16 Oct 2009, 14:54
SolidThink

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

big thanks
16 Oct 2009, 16:08
LocoDelAssembly
Your code has a bug

Joined: 06 May 2005
Posts: 4624
Location: Argentina
LocoDelAssembly 16 Oct 2009, 17:21
Just for the record, also a naive method: http://board.flatassembler.net/topic.php?p=96788#96788
16 Oct 2009, 17:21
pal

Joined: 26 Aug 2008
Posts: 227
pal 16 Oct 2009, 17:50
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.
16 Oct 2009, 17:50
windwakr

Joined: 30 Jun 2004
Posts: 827
windwakr 16 Oct 2009, 18:30
I think you have me mistaken with someone else. I can't even pronounce that!

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

_________________
----> * <---- My star, won HERE
16 Oct 2009, 18:30
pal

Joined: 26 Aug 2008
Posts: 227
pal 16 Oct 2009, 19:07
Ahh 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.
16 Oct 2009, 19:07
windwakr

Joined: 30 Jun 2004
Posts: 827
windwakr 16 Oct 2009, 19:14
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
16 Oct 2009, 19:14
pal

Joined: 26 Aug 2008
Posts: 227
pal 16 Oct 2009, 19:21
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
16 Oct 2009, 19:21
SolidThink

Joined: 16 Oct 2009
Posts: 23
SolidThink 17 Oct 2009, 00:38
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

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

17 Oct 2009, 00:38
pal

Joined: 26 Aug 2008
Posts: 227
pal 17 Oct 2009, 11:41
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.
17 Oct 2009, 11:41
SolidThink

Joined: 16 Oct 2009
Posts: 23
SolidThink 17 Oct 2009, 23:10
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

17 Oct 2009, 23:10
 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

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

Copyright © 1999-2024, Tomasz Grysztar. Also on GitHub, YouTube.

Website powered by rwasa.