Index
> Windows > Prime Numbers |
| Author |
|
|
Madis731 16 Oct 2009, 14:54
|
|||
16 Oct 2009, 14:54 |
|
|
SolidThink 16 Oct 2009, 16:08
Madis731 wrote: http://board.flatassembler.net/topic.php?t=7153 big thanks  |
|||
|
16 Oct 2009, 16:08 |
|
|
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 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 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. |
|||
|
16 Oct 2009, 18:30 |
|
|
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 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....
|
|||
|
16 Oct 2009, 19:14 |
|
|
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 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 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 17 Oct 2009, 23:10
pal wrote:
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 |
|
< Last Thread | Next Thread > |
Forum Rules:
|