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":
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)
;---------------------------------------------------------------
; 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]
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 ?
Hi,
thanks for reply!
The functionality to print the primes found is already there, I commented out:
;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
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.
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:
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
.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
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.
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
Quote from: hutch-- on July 30, 2008, 12:55:07 PM
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:
uval MACRO lpstring ; string to unsigned 32 bit integer
invoke atodw, reparg(lpstring)
EXITM <eax>
ENDM
val equ <uval>
: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.
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.
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)
;invoke WriteFile,hFile,ADDR szPrim,10,ADDR rlen,NULL
or DWORD
;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
Quote from: hutch-- on July 30, 2008, 05:09:06 PMyou 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.
I also got the same error, and corrected it substituting uval for val. In the macros.asm I am using val is defined as:
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.
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.
; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤
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
It also would not compile for me... uval worked fine. Interesting program. :U
Cobold, did you accidentally forget to attach that updated .zip file?
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.
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
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