Sieve of Eratosthenes several variations

[ognil]

Just my five cents

Code Select Expand

; Sieve of Eratosthenes in MASM64

include  \masm64\include64\masm64rt.inc

.data
    n      dq 1000000               ; Limit for prime numbers
    sqrt_n dq 3e8h                  ; Square root of n
    sieve  db 1000000 dup(1)        ; Sieve array, initialized to 1 (true)

.code
align 16
db  3 dup(90h)
entry_point proc
; Calculate sqrt(n)
   ; fild n
   ; fsqrt
   ; fistp sqrt_n

; Initialize  registers
    mov     rdx, 2                  ; Start from the first prime number
    lea     r8,  sieve
    mov     r9,  n                  ; r9 = Limit for prime numbers
@loop:
    cmp     byte ptr [r8+rdx],1     ; Check if sieve[rdx] is 1 (true)
    mov     rax, rdx
    jne     @next
    nop
    imul    rax, rax
    nop
@@:
    mov     byte ptr [r8+rax], 0    ; Mark multiples of rax as 0 (false) Set sieve[rax] to 0
    add     rax, rdx
    cmp     rax, r9                 ; r9 = Limit for prime numbers
    jb      @b
@next:
    add     rdx, 1
    cmp     rdx, 3e8h               ; sqrt_n = 3e8h
    jbe     @loop
    xor     rcx, rcx
    call    ExitProcess             ; Exit the program
entry_point endp

end

[zedd151]

Just my five cents

32 bit conversion below. I hope that you don't mind.
After a couple changes, the prime listing is 100% accurate. 

[zedd151]

I have converted ognils 64 bit code to 32 bit.
And I made a change by preinitialising the .data section array so all even numbers are pre-initialized to zero, and marked 1 as non prime, and 2 as prime manually in the code..

Added function to print the prime numbers. Use Console Assemble & Link.

Code Select Expand

; Sieve of Eratosthenes - ognil
; 32 bit conversion by zedd151 - also added code to print results, and a couple other adjustments

include  \masm32\include\masm32rt.inc

.data
    n       dd 1000000               ; Limit for prime numbers
    sqrt_n  dd 1000                  ; Square root of n

      ; array is now 250000 dwords, but will use it bytewise.
      ; we mark initialize all even numbers to zero.
     
    sieve   dd 250000 dup(01000100h)  ; Sieve array, initialized to 00, 01, 00, 01, etc.
    time1   dd 0
.code

PrimeSieve proc
    push ebx
    push edi
    xor edx, edx                     ; set edx to 2
    inc edx                          ; doing it this way aligns both loops to 4
    inc edx                          ; Start from the first prime number
    lea     edi,  sieve
    mov     byte ptr [edi+1], 0      ; mark 1 as not prime
    mov     byte ptr [edi+2], 1      ; mark 2 as prime
    mov     ebx,  n                  ; ebx = Limit for prime numbers
    nop                              ; padding to align loops to 4 bytes
    nop
@loop:
    cmp     byte ptr [edi+edx],1     ; Check if sieve[edx] is 1 (true)
    mov     eax, edx
    jne     @next
    nop
    imul    eax, eax
@@:
    mov     byte ptr [edi+eax], 0    ; Mark multiples of eax as 0 (false) Set sieve[eax] to 0
    add     eax, edx
    cmp     eax, ebx                 ; ebx = Limit for prime numbers
    jb      @b
@next:
    add     edx, 1
    cmp     edx, 3e8h                ; sqrt_n = 3e8h
    jbe     @loop
    pop edi
    pop ebx
    ret
PrimeSieve endp

PrintPrimes proc
    push ebx
    push edi
    lea edi, sieve
    xor ebx, ebx
  @@:
    cmp byte ptr [edi+ebx], 0
    jz noprint
    print str$(ebx), 13, 10
  noprint:
    inc ebx
    cmp ebx, n
    jnz @b
    pop edi
    pop ebx
    ret
PrintPrimes endp

start:
 
    CALL PrimeSieve                  ; just for NoCforMe!
    call PrintPrimes                 ;  :)
    push 0
    call    ExitProcess              ; Exit the program

end start

1219 milliseconds for 1000 iterations for range 0-1000000

1.2 microseconds to get primes from 0-1000000. Very fast indeed.