eratosthenes for training purpose

[cobold]

Hi,

I stumbled upon an old pseudo-code-source with a variation of the "sieve of eratosthenes" on the web and simply "translated" this to asm.
Does any expierienced person out there have any suggestions how this can be optimized?

"PSEUDO-CODE":

Code Select Expand


const N = 10000
var gestrichen: array [2..N] of boolean

{ Initialisierung des Primzahlfeldes: }
{ Alle Zahlen im Feld sind zu Beginn nicht gestrichen. }
for i = 2 to N do
  gestrichen[i] = false
end

i = 2
while i*i <= N
do
  if not gestrichen[i]
  then
    // i ist prim, streiche seine Vielfache mit i*i beginnend:
    for j = i*i to N by i
    do
      gestrichen[j] = true
    end
  endif
  i = i+1
end

for i = 2 to N do
  if not gestrichen[i] then
    print i; ", ";
end

MyASM-CODE: (just the loops, that is post is not too long)

Code Select Expand


;---------------------------------------------------------------
; Sieve - translated from PSEUDO to ASM
;---------------------------------------------------------------
    mov ebx,2                               ; ebx = i
    mov eax,2
    mul eax                                 ; eax = i*i
align 4
    .while eax < cByt                       ; while i*i < N
        .if byte ptr[esi+ebx]==0            ;   if not gestrichen[i] then
            mov edx,eax                     ;     j = i
            .while edx < cByt               ;     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
    invoke DumpArray,esi    ; process bytearray, inc primesfound for every
                            ; number that is not 'gestrichen' (deleted)


Tested the code extensively, results are okay:
Finds 5,761,455 primes from 2 to 100.000.000 in 16,7 secs on my ATHLON XP 2200 (@1792 Mhz)
ECPRIME (a program I found (exe-only):
C:\Asm>ecprime 100000000

100%
primes: 5761455
time: 0.050 sec

performs A LOT faster. How that?




[attachment deleted by admin]

[hutch--]

cobold,

It looks fine, speed is excellent. I woder if it would be a big deal to display the results so it can be redirected to a file ?

[cobold]

Hi,

thanks for reply!
The functionality to print the primes found is already there, I commented out:

Code Select Expand


;print str$(ebx),9


from the source I posted, because printing the results is not good for time-measurement.
Just remove the ";" in the line print str$(ebx),9 in proc DumpArray and it'll show you all the primes found!


rgds cobold

[jj2007]

Hi cobold,
Your source throws an error (Masm v10 of 26.05.2008):

tmp_file.asm(21) : error A2039: line too long

    mov cByt, val(input())
    .if cByt==0
        mov cByt,100000000        ; 7.1 seconds
    .endif

mov cByt, 0 will do the job.

[cobold]

Hello jj,

I am using Masm V9 and have no error. So I am sorry, but I can't figure out what's the problem.
The error in line 21 you mentioned refers to:

Code Select Expand

mov cByt,val(input())

but this is a correct statement. It asks the user for a number and stores the users answer to cByt, compiles fine with Masm v9.

and

Code Select Expand

    .if cByt==0
        mov cByt,100000000        ; 7.1 seconds
    .endif


Should not be a problem either: If user entered zero mov 100.000.000 to cByt. What do mean with 7.1 seconds?
Perhaps Masm V10 needs spaces, i.e .if cByt == 0 instead of .if CByt==   ?? I don't know!

Pls tell me when you found out what was wrong.

rgds
cobold

[hutch--]

I had no problems building it with ML 6.14. Uncomented the print command, put 13,10 at the end and ran it on primes up to 100 milion, fast and good results.

I actually hae a use for a tool like this as table of primed are very useful for hash tables.

[PBrennick]

Hi Cobold,
It works fine for me, also. I am not one of those optimizing type persons so maybe they would know better than I do; but, it seems to be quite acceptable in terms of speed considering the magnitude of the job.

-- Paul

[jj2007]

I had no problems building it with ML 6.14.

I don't want to spoil the party, but it chokes for me on the val part, both in v9 and v10, with ML 6.14:

    mov cByt,input() ; works fine but is not sufficient
    mov cByt,val(cByt) ; chokes
    mov cByt,val(input()) ; chokes

    mov cByt,uval(input()) ; works!

From my \masm32\macros\macros.asm:

Code Select Expand

      uval MACRO lpstring       ; string to unsigned 32 bit integer
        invoke atodw, reparg(lpstring)
        EXITM <eax>
      ENDM

      val equ <uval>


[hutch--]

 :bg

> I don't want to spoil the party

You haven't, it built correctly the first time with no modifications, you must have changed something somewhere.

[GregL]

I got the same error as jj using the downloaded file, with ML 6.14 and 6.15. Changing val to uval got rid of the error. I'm using MASM32 10 Beta i.
 

[cobold]

Hi fellows,

to everbody: thanks for comments
+++
to jj2007: can't duplicate your troubles with 'val', or 'uval' but have changed programm to use uval (because, and here you are right - there are no negative primes, so we don't need signed-value)  :wink
+++
to hutch: I have added code to store the primes either in ASCII (produces LARGE file, but human-readable)

Code Select Expand

;invoke WriteFile,hFile,ADDR szPrim,10,ADDR rlen,NULL
or DWORD

Code Select Expand

;invoke WriteFile,hFile,ebx,4,ADDR rlen,NULL
hutch: I think saving the DWORDS this way, you could create an obj-file and link that as hash table into your programs?
Anyway, I commented out all statements regarding file-operations, so that you don't get 400MB primes.txt file!  :green

Besides, I commented the code thoroughly to enhance readability and asisst other learners in the 'Campus'.

*** I ALSO FOUND A BUG, WHICH I REMOVED, of course! ***
The bug was: Array starts with offset zero, so I have to allocate cByt+1, otherwise the search goes from 0...cByt-1 - and this was not my intention  :U
I think the algo works reliable now, but if someone finds a bug, or enhancement, pls tell me!

sieb1new.zip - attached

nice day to everbody!

cobold

[jj2007]

you must have changed something somewhere.

Yeah, I did: I deleted the C: in c:\masm32\include\masm32rt.inc

Tried on three different machines, and even with QE - no success. It's the val.

[MichaelW]

I also got the same error, and corrected it substituting uval for val. In the macros.asm I am using val is defined as:

Code Select Expand


      uval MACRO lpstring       ; string to unsigned 32 bit integer
        invoke atodw, reparg(lpstring)
        EXITM <eax>
      ENDM

      val equ <uval>


Experimenting with ML 6.14 I cannot find any coding that will allow me to access a macro function through an equate.

[hutch--]

I built the example as it was posted which cotained the "val" around the "input" macro and it builds correctly as is with ML 6.14 and the old Microsoft linker. The val equate seems to work fine with the uval macro so i don't know what is happening.

LATER

It appears to be an order issue, this works where the macro and equates below the masm32rt.inc line failed with a line too long error.

Code Select Expand


; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤

    uuuval MACRO lpstring       ; string to unsigned 32 bit integer
      invoke atodw, reparg(lpstring)
      EXITM <eax>
    ENDM

    myval equ <uuuval>
    yourval equ <uuuval>
    anyval equ <uuuval>
    thisval equ <uuuval>

; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤
    include \masm32\include\masm32rt.inc
; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤

comment * -----------------------------------------------------
                        Build this  template with
                       "CONSOLE ASSEMBLE AND LINK"
        ----------------------------------------------------- *

    .code

start:
   
; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤

    call main
    inkey
    exit

; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤

main proc

    mov eax, myval("1234")
    print str$(eax),13,10

    mov eax, yourval("4321")
    print str$(eax),13,10

    mov eax, anyval("5678")
    print str$(eax),13,10

    mov eax, thisval("8765")
    print str$(eax),13,10

    ret

main endp

; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤

end start


[Mark Jones]

It also would not compile for me... uval worked fine. Interesting program. :U

Cobold, did you accidentally forget to attach that updated .zip file?