eratosthenes for training purpose

[MichaelW]

I was going to compare the cycle counts for several different versions, but the code that I had was so much slower that I was ashamed to include it. Running on a P3, I get 392 cycles to generate the first 25 primes, and if that seems like a lot, consider that the outer loop is running 8 times and the inner loop a total of 99 times.

Code Select Expand


; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
    include \masm32\include\masm32rt.inc
    .686
    include \masm32\macros\timers.asm
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
    .data
    .code
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

sieve proc pflags:DWORD, nflags:DWORD
    push ebx
    push esi
    mov esi, pflags
    mov ebx,2                               ; ebx = i
    mov eax,2
    mul eax                                 ; eax = i*i
    align 4
    .while eax < nflags                     ; while i*i < N
        .if byte ptr[esi+ebx]==0            ;   if not gestrichen[i] then
            mov edx,eax                     ;     ebx = j
            .while edx < nflags             ;     for j = i*i to N
                mov byte ptr[esi+edx],1     ;        gestrichen[j] = true
                add edx,ebx
            .endw
        .endif
        inc ebx                             ; i = i+1
        mov eax,ebx
        mul eax                             ; eax = i*i
    .endw
    pop esi
    pop ebx
    ret
sieve endp

; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
start:
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
    mov ebx, alloc(10000)
    invoke sieve, ebx, 7920
    mov esi, 2
    .WHILE esi < 7920
      .IF BYTE PTR [ebx+esi] == 0
        print ustr$(esi),9
      .ENDIF
      inc esi
    .ENDW
    free ebx

    print chr$(13,10,13,10)
    print "generating 1000000 primes ...",13,10

    mov ebx, alloc(15485864)
    timer_begin 1, HIGH_PRIORITY_CLASS
      invoke sieve, ebx, 15485864
    timer_end
    print ustr$(eax),"ms",13,10
    ; 1000000th prime should be 15485863.
    mov esi, 15485863
    .WHILE esi < 15485864
      .IF BYTE PTR [ebx+esi] == 0
        print ustr$(esi),13,10
      .ENDIF
      inc esi
    .ENDW
    free ebx

    print "generating 10000000 primes ...",13,10
    mov ebx, alloc(1794246734)
    timer_begin 1, HIGH_PRIORITY_CLASS
      invoke sieve, ebx, 179424674
    timer_end
    print ustr$(eax),"ms",13,10
    ; 10000000th prime should be 179424673.
    mov esi, 179424673
    .WHILE esi < 179424674
      .IF BYTE PTR [ebx+esi] == 0
        print ustr$(esi),13,10,13,10
      .ENDIF
      inc esi
    .ENDW
    free ebx

    invoke Sleep, 3000

    mov esi, alloc(100000)
    push esi
    counter_begin 1000, HIGH_PRIORITY_CLASS
      invoke sieve, esi, 98
      add esi, 100
    counter_end
    print ustr$(eax)," cycles, first 25 primes",13,10,13,10
    pop esi
    free esi

    inkey "Press any key to exit..."
    exit
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
end start

1           2
10          29
100         541
1000        7919
10000       104729
100000      1299709
1000000     15485863
10000000    179424673
100000000   2038074743
1000000000  22801763489