Eratosthenes x86アセンブリのふるい

Question

私はアセンブリの初心者ですが、Erathothenesの篩を実装しようとしていますが、コードはありますが、それは1と600の間でしか動作しません。何故ならn = 1000を置くと、完全なコード、任意のヘルプが行います。

Include Irvine32.inc 
n=1000 

.data 
prime DWORD n DUP(?) 

.code 
main PROC 
     mov ecx,n  ;initialize ecx to 1000 
     mov esi, OFFSET prime 
;-------------------------------------------------------- 
; Initialize Array with 1's 
;-------------------------------------------------------- 
FillArray: mov eax,1 
     mov [esi],eax 
     mov eax,[esi] 
     add esi,TYPE DWORD    ;4 to jump to the next index 
     loop FillArray 

    mov ebx,8 
    mov edx,0 
    mov ecx,n 
    mov ebp,2 
    mov esi,0 
;---------------------------------------------------------------- 
; Sieve 
;---------------------------------------------------------------- 
SIEVE:  mov eax,prime[ebx] 
     mov edx,ebx 
     mov edi,ebx 
     add edx,edi     ;j=i+i 
     mov esi,ebp 
     mov ecx,n 
     sub ecx,ebp 
     add ecx,2 
     add ebx,TYPE DWORD 
     cmp eax,1 
     je FLIP 
     inc ebp 
     loop SIEVE 
     jmp K 

FLIP:  mov eax,0 
     mov prime[edx],eax 
     add edx,edi 
     cmp esi,n 
     jg SIEVE 
     add esi,ebp 
     loop FLIP 

K: 

    mov esi, OFFSET prime 
    mov ecx,n 
    sub ecx,2 
    mov ebx,1 
    mov edx,8   ;Start checking from index of second element 

PRINT: mov eax,prime[edx]   ; 
     add edx,TYPE DWORD 
     inc ebx 
     cmp eax,1 
     jne H 
     mov eax,ebx 
     call WriteDec 
     call Crlf 
     loop PRINT 
     jmp D 
H: loop PRINT 
D: 
    exit 

main ENDP 
END main 

Answer 1

あなたは手段を「めちゃくちゃ行く」何と十分に特異的ではなかった、とあなたはおそらくあなたのコードをデバッグしていない、またあなたが従うことは、それが簡単にするために十分なことをコメントし、その数分後、私はそれを見て私の本能に従った。私の本能は、最初から始め、それを普通の方法で書くようにと言っていた。

これがあなたに役立つかどうか - 私は多分、それほど考えられないでしょう。

は、しかし、私はこのがと「任意の助けがどうなる」タイトル「ふるいエラトステネスのx86のアセンブリ」との質問に対して有効な回答であると考えています。

ここであなたは、完全に外国の情報源を理解しようとし、使用されたアイデアをつかむようにしてください。あなた自身のコードを書くときに役立つようになるでしょう。がんばろう。 :)

最初のことは、先に数学的にタスクをクリーンアップする必要があります。

あなたが望むならば、sqrt（n）の値を超えて「ふるい分け」する必要はありません。 SQRT（N）が素数である場合ので、その乗算2 * SQRT（n）は、3 *のSQRT（N）、...、previous_primeの*のSQRT（n）は、すでにこれらの小さいから "ふるいにかけた" されている

ループの前半でふるい分ける素数。

最初の「まだunsieved」番号はsqrt（n）* sqrt（n）です。それはnで、それは配列境界外です。したがって、sqrt(n)が整数に切り捨てられているので、特殊な "n"（整数はsqrt（n））のため、sqrt(n)が整数に切り捨てられているので、数値が=>sqrt（n）に達すると、）私はN一度自体「ふるい」にしようとしますが、それはflip_loop内部テストによって検出され、いずれにしても終了します。

---

Include Irvine32.inc 
n=1000 
n_terminal=31 
    ; terminal compare value is min(sqrt(n), 0FFFFh) (last value to process) 
    ; no point to sieve beyond sqrt(n), because first unset multiply is 
    ; sqrt(n)*sqrt(n) = n => beyond array 
    ; and no point to sieve 10000h, because 10000h*10000h is out of 32b 

.data 
prime BYTE n DUP(?) 

.code 
main PROC 
    ; fill array with "1" (from number 2 to n) 
    mov edi,OFFSET prime+2 
    mov ecx,n-2 
    mov eax,1   ; eax=1 will be used also later (also ah=0) 
    rep stosb 
    ; set "0" and "1" as non-prime too 
    mov WORD PTR [prime],cx ; (cx == 0 after "rep stosb") 
    ; set "0" to all other non-primes by sieving 
    mov esi,eax  ; esi=1, start the loop as if "1" was handled last 
sieve_loop: 
    inc esi   ; next number to test 
    ; sqrt(n) is enough to process, beyond that n <= number*number => out of array 
    cmp esi,n_terminal 
    ja sieve_end  ; out of table, end sieving 
    cmp prime[esi],al ; compare with "1" 
    jne sieve_loop ; not a prime, don't flip the rest of sieve 
    ; esi is prime, flip the other multiplies of it, starting from esi*esi (!) 
    mov edi,esi  ; esi*esi as smaller multiples are already covered by 
    imul edi,edi  ; smaller prime numbers sieving the array before 
flip_loop: 
    cmp edi,n   ; check if the multiply points beyond table 
    jae sieve_loop ; if yes, continue main loop with next "prime" 
    mov prime[edi],ah ; set this number to "0" (not prime) 
    add edi,esi  ; edi = next multiply of esi prime 
    jmp flip_loop 

sieve_end: 
    ; print all primes starting from 2 
    mov esi,eax  ; esi = 1, as if "1" was handled last 
print_loop: 
    inc esi   ; while (++number < n) 
    cmp esi,n 
    jae end_print_loop 
    cmp BYTE PTR prime[esi],1 ; eax/al is modified from "WriteDec" 
    jne print_loop ; not a prime number, loop 
    ; esi is prime number, print it 
    mov eax,esi 
    call WriteDec  ; these two calls must preserve esi 
    call Crlf 
    jmp print_loop 

end_print_loop: 
    exit 

main ENDP 
END main 

私はNASMとlinuxの下でそれをテストしたので、私でしたそれをコンパイルするために構文を少し変更してから、MASM/TASM + irvineの構文を元に戻す必要があったので、maybいくつかの小さなバグが変換中にそこに滑り落ちましたが、うまくいかない場合は教えてください。

Answer 2

これにはまだ問題がある人は、次のコードをPythonからアセンブリに実装しました。

from math import sqrt 

def FindPrimes(limit): 
    isPrime = {} 

    isPrime[1] = False 
    for i in range(2, limit + 1): 
     isPrime[i] = True 

    checkLimit = int(sqrt(limit)) + 1 
    for i in range(2, checkLimit): 
     if isPrime[i]: 
      for factor in range(2, limit + 1): 
       j = i * factor 
       if (j > limit): break 
       isPrime[j] = False 

    primes = [] 
    for i in range(1, limit + 1): 
     if isPrime[i]: 
      primes.append(i) 

    return primes 

リミット "「[1] isPrime」、そしてもちろん、次のアセンブリの実装はMASMにあり、我々は最初のDWORDを処理するので、それは、手動で入力平方根プラス1する必要がありますのでご注意くださいFindPrimes（制限）」を選択します。

.386 
.model flat,stdcall 
.stack 4096 
ExitProcess proto,dwExitCode:dword 

n=1000 
sqrt=32 

.data 
    sieveArray DWORD n DUP(0) 
    primeNumbers DWORD n DUP(0) 
    limit DWORD 0 
    varInnerLoop DWORD 0       ;variable j 
    falseValue DWORD 0 
    primerHelper DWORD 1 

.code 
main PROC 

    mov ecx,LENGTHOF sieveArray-1 
    mov edi,OFFSET sieveArray+TYPE DWORD*2 
    mov eax,1 

fillUp: 
    mov [edi],eax 
    add edi,TYPE DWORD 
    loop fillUp 

checkForPrime: 
    mov edi,OFFSET sieveArray+TYPE DWORD*2  ;reset for iteration 
    mov esi,[edi]        ;pointer helper 
    mov eax,TYPE DWORD       ;offset helper 
    mov ebx,1         ;counter for loopOverNumbers reference 
    mov ecx,sqrt-1        ;sqrt(limit)+1 `limit`¨, -1 because index 0 = index 1, counter 
    mov edx,1         ;outer loop variable helper for inner loop 

    loopOverNumbers: 
     cmp ebx,ecx 
     je iterateOverPrimes     ;take me out of the loop because I have iterated over range(1,edx) 
     cmp esi,1 
     pushad         ;save my flags for outer loop, specially ebx and ecx 
     je iterateOverFactorsSetUp 
     continueIteration: 
     popad 
     add edi,eax 
     mov esi,[edi] 
     inc edx 
     loop loopOverNumbers 

      iterateOverFactorsSetUp: 
       mov eax,1       ;factor for inner loop   
       mov ecx,n+1 

       iterateOverFactors: 
        cmp ebx,ecx 
        je continueIteration 
        push edx 
        push eax 
        inc eax       ;pointer must increment to reflect real value 
        inc edx       ;pointer must increment to reflect real value 
        imul edx,eax 
        mov varInnerLoop,edx   ;j = i * factor 
        cmp varInnerLoop,n    ;if (j > limit): break 
        jg continueIterationHelper 
        imul edx,TYPE DWORD 
        mov edi,OFFSET sieveArray 
        add edi,edx 
        mov eax,0 
        mov [edi],eax     ;reset to old value before pointer 
        pop eax 
        pop edx       
        inc eax 
        loop iterateOverFactors 

      continueIterationHelper:    ;have to pop eax and edx in order to get original values when returning to 
        pop eax 
        pop edx 
        jmp continueIteration 

iterateOverPrimes: 
    mov eax,TYPE DWORD 
    mov ecx,n+1        ;limit helper 
    mov ebx,0 
    mov edi,OFFSET sieveArray+TYPE DWORD 

    checkifPrime: 
     mov esi,[edi] 
     cmp esi,1 
     pushad 
     je appendToPrimeArray 
     continueSearch: 
     popad 
     add edi,eax 
     inc ebx 
     loop checkifPrime 
     jmp searchDone 

     appendToPrimeArray: 
      mov eax,TYPE DWORD 
      mov edi,OFFSET primeNumbers 
      imul eax,primerHelper      ;pointer for primeNumbers helper 
      add edi,eax 
      inc ebx 
      mov [edi],ebx 
      inc primerHelper 
      jmp continueSearch 

    searchDone: 


INVOKE ExitProcess,0 
main ENDP 
END main 

あなたの結果を確認するために、あなたはprimeNumbersを確認することができ、それが連続してDWORDとして、すべての素数を含んでいます。あなたが任意の懸念がある場合

私に知らせてください:)