Сито из Eratosthenes x86 Assembly

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 (п) простое, то его умножает 2 * SQRT (п), 3 * SQRT (п), ..., previous_prime * SQRT (п) уже "просеивают" от меньшего простые числа, просеивающие ранее в цикле.

Первый номер «все еще несчастливый» - это sqrt (n) * sqrt (n), то есть n сам, и это вне границ массива. Поэтому после достижения числа> = sqrt (n) вы можете закончить основной цикл алгоритма (я использую острый тест number > sqrt(n), потому что sqrt(n) усечен до целого числа, поэтому для специального «n» (с целым числом sqrt (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 

я проверить его под Linux с NASM, так что я пришлось немного изменить синтаксис, чтобы скомпилировать его, а затем изменить синтаксис для MASM/TASM + irvine, поэтому mayb e небольшая ошибка проскользнула там во время конвертации, сообщите мне, если это не сработает.

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 

Пожалуйста, обратите внимание, что после внедрения сборки в MASM и она требует от вас вручную ввести квадратный корень плюс 1, так как мы обрабатываем первый параметр DWORD как «IsPrime [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 последовательно.

Если у вас есть какие-либо проблемы, пожалуйста, дайте мне знать :)