Sieve of Eratosthenes several variations

[zedd151]

Changed the topic title, to reflect that several variations are available in this topic, by several authors. If you have a different Prime Sieve, post your code here and join the phun.

My 32 bit (original) version of Sieve of Eratosthenes... (added message box, if array not allocated.)

Code Select Expand

    include \masm32\include\masm32rt.inc
   
    .data
   
    pTbl        dd 0                    ; <-- pointer to byte array
    arrsize    dd 1000000
    curnumber  dd 0                    ; <-- current number for our sieve algo
   
    .code
start:
   
    invoke GlobalAlloc, GPTR, arrsize  ; <-- allocate memory for table and prime numbers
  .if eax == 0                          ; <-- if not enough memory for array size, display message and exit
 
    fn MessageBox, 0, "Not enough memory to create array", 0, 0
    jmp noarray
  .endif
    mov pTbl, eax
   
    push edi
    mov edi, pTbl                      ; temporarily put ptr to array in edi, for stosb
    mov eax, 01010101h
    mov ecx, arrsize
    shr ecx, 2
    rep stosd                          ; <-- initialize the table to '1'
    pop edi                            ; <-- restore edi to previous value
    mov esi, pTbl                      ; <-- we put ptr to array into esi :)
   
    xor eax, eax
    mov curnumber, 2                    ; <-- exluding '0' and '1', as neither are prime
    add eax, curnumber                  ; <-- exclude the first iteration of sequence
                                        ; <-- else we will have no primes listed
  @@:
    add eax, curnumber                  ; <-- get multiples for this iteration
    cmp eax, arrsize                    ; <-- check if end of array is reached, exit
    jae done1                          ;    loop if yes.
    cmp byte ptr [esi+eax], 0          ; <-- check if array location is already marked
    jz @b
    mov byte ptr [esi+eax], 0          ; <-- if not marked, we mark it now
    jmp @b
   
  done1:
    inc curnumber                      ; <-- increment current number
    mov eax, curnumber                  ; <-- move it into register
    cmp eax, arrsize                    ; <-- check if at array end
    jae done2                          ; <-- jump to next process, if array end
    xor eax, eax                        ;    else increment to next number
    add eax, curnumber
    jmp @b                              ; <-- jump back into the processing loop
   
  done2:
    mov edi, 2                          ; <--- skip over '0' and '1'
  @@:
   
    cmp byte ptr [esi+edi], 1          ; <--- if byte == zero, not prime, don't print
    jnz noprint
   
    mov eax, ustr$(edi)                ; <--- convert our current prime to ascii decimal string
   
    pushad                              ; <--- save all the registers

    print eax, 0Dh, 0Ah, 0
   
    popad                              ; <--- restore the registers
   
  noprint:
    inc edi
    cmp edi, arrsize
    jl @b                              ; <--- loop back to get more primes to print
    invoke GlobalFree, pTbl            ; <--- free the memory used

  noarray:                              ; <--- jump here to exit, if memory not allocated
    invoke ExitProcess, 0
end start

Use the included "makeit.bat" to assemble and link it, and "RunIt.bat" to run the program, generate file "primes32.txt", and open the .txt file with qeditor.

You're Welcome. 

[jj2007]

Great stuff, Zedd

[zedd151]

Great stuff, Zedd

Thanks, but it is actually old code, I found it recently ('prime' was nowhere in its original name  ). Previously, I only knew where my more recent 64 bit version was. 

[FORTRANS]

Hi,

   I wrote a program to display primes as white pixels on a
black background.  I varied the width of the picture to look
for "patterns" that would show up at times.  A fun, if a bit
crude, exercise.  A DOS program with VESA graphics.  Humans
can see (false) patterns in some random data.

Cheers,

Steve N.

[zedd151]

Hi,

  I wrote a program to display primes as white pixels on a
black background.  I varied the width of the picture to look
for "patterns" that would show up at times.  A fun, if a bit
crude, exercise.  A DOS program with VESA graphics.  Humans
can see (false) patterns in some random data.

Cheers,

Steve N.

Hi Steve. Interesting. I am sure that daydreamer would like to see that code, if it is still available. Magnus (daydreamer) has been experimenting with displaying the primes as a bitmap. Seems very similar to your idea, unless of course I misunderstood Magnus' discussion and intention regarding prime numbers and using bitmaps.
Magnus? What say you?

[daydreamer]

Hi,

  I wrote a program to display primes as white pixels on a
black background.  I varied the width of the picture to look
for "patterns" that would show up at times.  A fun, if a bit
crude, exercise.  A DOS program with VESA graphics.  Humans
can see (false) patterns in some random data.

Cheers,

Steve N.

Hi Steve. Interesting. I am sure that daydreamer would like to see that code, if it is still available. Magnus (daydreamer) has been experimenting with displaying the primes as a bitmap. Seems very similar to your idea, unless of course I misunderstood Magnus' discussion and intention regarding prime numbers and using bitmaps.
Magnus? What say you?

here is 1 bit/pixel bitmap drawing/output I was going to use as starting point
512kb*8 pixels/byte and few bytes overhead its possible to store lots of primes

[zedd151]

I had to fix the path for "ptexture.inc", and used "console assemble and link".

Well, at least its a start. The resulting bmp looks like a two lane highway, 
Now to implement this bitmap code in your prime numbers code for display. 

[TimoVJL]

Well, at least its a start. The resulting bmp looks like a two lane highway, 

After earthquake 

[zedd151]

Well, at least its a start. The resulting bmp looks like a two lane highway, 

After earthquake 

lol
I'm pretty sure that Magnus was just testing the drawing functions and bitmap creation code prior to using those in the (hopefully near) future, for his prime number code.

[daydreamer]

Well, at least its a start. The resulting bmp looks like a two lane highway, 

After earthquake 

lol
I'm pretty sure that Magnus was just testing the drawing functions and bitmap creation code prior to using those in the (hopefully near) future, for his prime number code.

its reusing code I developed from Dos 13h 16bit code drawing different road tiles ->32bit code writing to .bmps instead
its already have compressing from a byte buffer to bits = 1/8 smaller data in writebmp proc
2 gb memory =17 179 869 184 pixels
3.8 gb memory 32 641 751 449 pixels

[zedd151]

its reusing code I developed from Dos 13h 16bit code drawing different road tiles ->32bit code writing to .bmps instead

Okay.   

[NoCforMe]

Here's my version, a li'l console program. Just spits the prime #s out with no formatting (left as an exercise for the reader).
A little neater than some other examples, perhaps.

Code Select Expand

;============================================
; -- Sieve of Erastothenes --
;
;============================================

.nolist
include \masm32\include\masm32rt.inc
.list

;============================================
; Defines, structures, prototypes, etc.
;============================================

Sieve PROTO maxNum:DWORD, primeBuffPtr:DWORD

$primeMarker EQU -1 ;Marker to indicate a prime # in buffer.
$CRLF EQU <13, 10>
$tab EQU 9


;============================================
; HERE BE DATA
;============================================
.data

UsageMsg DB $CRLF, "Usage: sieveoferastothenes #", $CRLF
DB $tab, "where ""#"" is the maximum # to search for primes.", $CRLF, $CRLF, 0

;============================================
; UNINITIALIZED DATA
;============================================
.data?

HeapHandle HANDLE ?
PrimeBuffer DD ? ;Base address of heap-allocated buffer.
CmdLineBuffer DB 256 DUP(?)


;============================================
; CODE LIVES HERE
;============================================
.code

start: CALL WinMain
INVOKE ExitProcess, 0


;====================================================================
; Mainline proc
;====================================================================

WinMain PROC
LOCAL maxNum:DWORD, currNum:DWORD, numBuffer[16]:BYTE

; Get max. prime # from command line:
INVOKE GetCL, 1, OFFSET CmdLineBuffer ;Get arg[1] from command line.
CMP EAX, 1 ;See how many args on CL.
JE getnum

; No arg. given, so show "usage" message:
INVOKE StdOut, OFFSET UsageMsg
JMP exit99

getnum: INVOKE atodw, OFFSET CmdLineBuffer
MOV maxNum, EAX

; Allocate a buffer for primes:
CALL GetProcessHeap
MOV HeapHandle, EAX

INVOKE HeapAlloc, EAX, 0, maxNum
MOV PrimeBuffer, EAX

; Find those primes!
INVOKE Sieve, maxNum, PrimeBuffer

; Show those primes!
MOV EBX, PrimeBuffer
MOV currNum, 1

showlp: CMP BYTE PTR [EBX], 0 ;Next # in prime buffer.
JE skip ;  Nope, skip it.
INVOKE dwtoa, currNum, ADDR numBuffer
INVOKE StdOut, ADDR numBuffer
MOV WORD PTR numBuffer, " " ;Put a space between #s.
INVOKE StdOut, ADDR numBuffer

skip: ADD currNum, 2
ADD EBX, 2 ;Skip all even #s.
MOV EAX, currNum
CMP EAX, maxNum
JBE showlp

INVOKE HeapFree, HeapHandle, 0, PrimeBuffer

exit99: RET

WinMain ENDP


;=========================================================================
; Sieve (maxNum, primeBuffPtr)
;
; Here's the Sieve of Erastothenes, a method of finding all prime #s in a
; given range.
;
; The buffer passed in and returned with all primes marked out starts at
; 1, not 0.
;
; Prime numbers in the buffer are marked with a value of -1 (0FFh).
;=========================================================================

Sieve PROC maxNum:DWORD, primeBuffPtr:DWORD

; Initialize prime buffer to all primes (mark with -1):
MOV ECX, maxNum
MOV EDX, primeBuffPtr
MOV AL, $primeMarker
initlp: MOV [EDX], AL
INC EDX
LOOP initlp

; Starting at #4, mark out all even #s as not prime:
MOV ECX, primeBuffPtr
MOV EDX, ECX
ADD ECX, maxNum ;Get our stopping point.
ADD EDX, 3 ;Point to #4 (buffer starts @ 1).
nxtevn: MOV BYTE PTR [EDX], 0 ;Mark as not prime.
ADD EDX, 2 ;Jump by 2s.
CMP EDX, ECX ;Continue until
JB nxtevn ;  we're @ end o'buffer.

; Here's the Sieve code: starting @ #3, mark out all multiples:
MOV EDX, primeBuffPtr
MOV ECX, 3 ;ECX = current number (start @ 3).
MOV EAX, ECX ;EAX = # to add to create multiples.
multlp: ADD ECX, EAX ;Next multiple.
CMP ECX, maxNum ;Are we at the end of buffer?
JA nxtmul ;  Yep, done with these multiples.
MOV BYTE PTR [EDX + ECX - 1], 0 ;  Nope, mark out as not prime.
JMP multlp ;Next multiple.

; Finished a set of multiples--go to next set:
nxtmul: ADD EAX, 2 ;Skip over even #s.
CMP EAX, maxNum ;Are we @ the last #?
JAE done ;  Yep, we be outta here.
MOV ECX, EAX ;  Else process that #s multiples.
JMP multlp

done: RET

Sieve ENDP

END start


[zedd151]

Seems a slight error in your version. '2' should be present as the only even number. '1' should not be there.

Code Select Expand

1
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
101I replaced the " " (space) in your code with a single byte "0Dh" for carriage return for better printout.

Should be...

Code Select Expand

2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
101


[NoCforMe]

Ack. I forgot about 2!

[zedd151]

Ack. I forgot about 2!

   it happens.