Microsoft 64 bit MASM > Examples
Prime sieve 64 bit
zedd151:
First trial. converted (literally) my 32 bit prime sieve program to 64 bit.
It works as is, but I am certain it could be a little more 'politically correct' for 64 bit land.
So any comments or help in steering me in the right direction will be mucho appreciated.
--- Code: --- include \masm32\include64\masm64rt.inc
.data
pTbl dq 0
arrsize dq 104
curnumber dq 0
.code
start proc
invoke GlobalAlloc, GPTR, arrsize
cmp rax, 0
jz noarray
mov pTbl, rax
mov rsi, pTbl
xor rax, rax
mov cl, 1
@@:
mov byte ptr [rsi+rax], cl
inc rax
cmp rax, arrsize
jl @b
xor rax, rax
mov curnumber, 2
add rax, curnumber
@@:
add rax, curnumber
cmp rax, arrsize
jae done1
cmp byte ptr [rsi+rax], 0
jz @b
mov byte ptr [rsi+rax], 0
jmp @b
done1:
inc curnumber
mov rax, curnumber
cmp rax, arrsize
jae done2
xor rax, rax
add rax, curnumber
jmp @b
done2:
mov rdi, 2
@@:
cmp byte ptr [rsi+rdi], 1
jnz noprint
mov rax, str$(rdi)
conout rax, lf
noprint:
inc rdi
cmp rdi, arrsize
jl @b
invoke GlobalFree, pTbl
noarray:
invoke ExitProcess, 0
start endp
end
--- End code ---
removed non working link
zedd151:
First changes. Initializing the array a qword at a time, rather than byte wise. All numbers divisible by 2 are marked non prime. All others marked as potential prime, until we run the sieve.
--- Code: ---
include \masm32\include64\masm64rt.inc
.data
pTbl dq 0
arrsize dq 1000h ; must be divisible by 8 ;)
curnumber dq 0
.code
start proc
invoke GlobalAlloc, GPTR, arrsize
cmp rax, 0
jz noarray
mov pTbl, rax
mov rsi, pTbl
xor rax, rax
mov rcx, 0100010001000100h ; 8 bytes at a time :)
@@:
mov qword ptr [rsi+rax], rcx
add rax, 8
cmp rax, arrsize
jl @b
xor rax, rax
mov byte ptr [rsi+rax+2], 1 ; mark '2' as prime
mov curnumber, 3 ; skip multiples of 2
add rax, curnumber
@@:
add rax, curnumber
cmp rax, arrsize
jae done1
cmp byte ptr [rsi+rax], 0
jz @b
mov byte ptr [rsi+rax], 0
jmp @b
done1:
inc curnumber
mov rax, curnumber
cmp rax, arrsize
jae done2
xor rax, rax
add rax, curnumber
jmp @b
done2:
mov rdi, 2
@@:
cmp byte ptr [rsi+rdi], 1
jnz noprint
mov rax, str$(rdi)
conout rax, lf
noprint:
inc rdi
cmp rdi, arrsize
jl @b
invoke GlobalFree, pTbl
noarray:
invoke ExitProcess, 0
start endp
end
--- End code ---
Attachment in above post already updated.
Instead of using a 'BYTE' array, how hard would it be to implement a 'bit' array? Since we only need '0' and '1' a bit array would be perfect.
We would need a fast decoding/encoding algo, especially in the upper regions with many iterations. That is for a future project though.
zedd151:
Big change this time. The section that marks 'non prime' now checks for even-ness of the incrementation counter. It will now increment to the next
number if even number in the counter is detected.
The attachment will not be updated you can update from this post. :)
--- Code: ---
include \masm32\include64\masm64rt.inc
.data
pTbl dq 0
arrsize dq 1000000h ; must be divisible by 8
curnumber dq 0
.code
start proc
invoke GlobalAlloc, GPTR, arrsize
cmp rax, 0
jz noarray
mov pTbl, rax
mov rsi, pTbl
xor rax, rax
mov rcx, 0100010001000100h ; 8 bytes at a time :)
@@:
mov qword ptr [rsi+rax], rcx
add rax, 8
cmp rax, arrsize
jl @b
xor rax, rax
mov byte ptr [rsi+rax+2], 1 ; mark '2' as prime
mov rcx, 3 ; skip multiples of 2
add rax, rcx
@@:
add rax, rcx
cmp rax, arrsize
jae done1
cmp byte ptr [rsi+rax], 0
jz @b
mov byte ptr [rsi+rax], 0
jmp @b
done1:
inc rcx
cmp rcx, arrsize
jae done2
mov dl, cl ; to check nibble for 0,2,4,6,8,A,C,E
and dl, 0Fh ; we will increment counter if even :)
cmp dl, 0 ; skipping iterating through even numbers
jz done1
cmp dl, 2 ; skipping iterating through even numbers
jz done1
cmp dl, 4 ; skipping iterating through even numbers
jz done1
cmp dl, 6 ; skipping iterating through even numbers
jz done1
cmp dl, 8 ; skipping iterating through even numbers
jz done1
cmp dl, 0Ah ; skipping iterating through even numbers
jz done1
cmp dl, 0Ch ; skipping iterating through even numbers
jz done1
cmp dl, 0Eh ; skipping iterating through even numbers
jz done1
xor rax, rax
add rax, rcx
jmp @b
done2:
mov rdi, 2
@@:
cmp byte ptr [rsi+rdi], 1
jnz noprint
mov rax, str$(rdi)
conout rax, lf
noprint:
inc rdi
cmp rdi, arrsize
jl @b
invoke GlobalFree, pTbl
noarray:
invoke ExitProcess, 0
start endp
end
--- End code ---
Next step will be to skip iterating through the even numbers during the print operations... :biggrin:
Little by little, we are getting there.....................
zedd151:
Now when either the 'prime marking' counter, or the print counter is an even number, we skip it and increment to the next value.
Should make the program a bit faster. I haven't timed it though. I don't have a reliable method just yet.
--- Code: --- include \masm32\include64\masm64rt.inc
.data
pTbl dq 0
arrsize dq 100000h ; must be divisible by 8
curnumber dq 0
.code
start proc
invoke GlobalAlloc, GPTR, arrsize
cmp rax, 0
jz noarray
mov pTbl, rax
mov rsi, pTbl
xor rax, rax
mov rcx, 0100010001000100h ; 8 bytes at a time :)
@@:
mov qword ptr [rsi+rax], rcx
add rax, 8
cmp rax, arrsize
jl @b
xor rax, rax
mov byte ptr [rsi+rax+2], 1 ; mark '2' as prime
mov rcx, 3 ; skip multiples of 2
add rax, rcx
@@:
add rax, rcx
cmp rax, arrsize
jae done1
cmp byte ptr [rsi+rax], 0
jz @b
mov byte ptr [rsi+rax], 0
jmp @b
done1:
inc rcx
cmp rcx, arrsize
jae done2
mov dl, cl ; to check nibble for 0,2,4,6,8,A,C,E
and dl, 0Fh ; we will increment counter if even :)
cmp dl, 0 ; skipping iterating through even numbers
jz done1
cmp dl, 2 ; skipping iterating through even numbers
jz done1
cmp dl, 4 ; skipping iterating through even numbers
jz done1
cmp dl, 6 ; skipping iterating through even numbers
jz done1
cmp dl, 8 ; skipping iterating through even numbers
jz done1
cmp dl, 0Ah ; skipping iterating through even numbers
jz done1
cmp dl, 0Ch ; skipping iterating through even numbers
jz done1
cmp dl, 0Eh ; skipping iterating through even numbers
jz done1
xor rax, rax
add rax, rcx
jmp @b
done2:
mov rdi, 2
@@:
cmp byte ptr [rsi+rdi], 1
jnz noprint
mov rax, str$(rdi)
conout rax, lf
noprint:
inc rdi
cmp rdi, arrsize
jz outtahere
mov dl, byte ptr [rsi+rdi]
and dl, 0Fh ; we will increment counter if even :)
cmp dl, 0 ; skipping iterating through even numbers
jz noprint
cmp dl, 2 ; skipping iterating through even numbers
jz noprint
cmp dl, 4 ; skipping iterating through even numbers
jz noprint
cmp dl, 6 ; skipping iterating through even numbers
jz noprint
cmp dl, 8 ; skipping iterating through even numbers
jz noprint
cmp dl, 0Ah ; skipping iterating through even numbers
jz noprint
cmp dl, 0Ch ; skipping iterating through even numbers
jz noprint
cmp dl, 0Eh ; skipping iterating through even numbers
jz noprint
jmp @b
outtahere:
invoke GlobalFree, pTbl
noarray:
invoke ExitProcess, 0
start endp
end
--- End code ---
edit = removed two unnecessary lines of code.
zedd151:
Latest version. Removed the 'nibble check' for even digits. Now incrementing counters by 2 instead. ::)
Also, this version writes directly to a file named 'Primes.txt' in the folder where the .exe is residing - just double click the exe!
Have fun!
--- Code: --- ; faster 'basic' 64 bit prime sieve
include \masm32\include64\masm64rt.inc
.data
pTbl dq 0
arrsize dq 10000 ; must be divisible by 8
curnumber dq 0
hPrimes dq 0
fName db "Primes.txt", 0
pfname dq 0
.code
start proc
invoke GlobalAlloc, GPTR, arrsize
cmp rax, 0
jz noarray
mov pTbl, rax
mov rsi, pTbl
xor rax, rax
mov rdi, rsi
add rdi, arrsize
mov rcx, 0100010001000100h ; 8 bytes at a time :)
align 16
@@:
mov qword ptr [rsi], rcx
add rsi, 8
cmp rsi, rdi
jge @f
jmp @b
@@:
mov rsi, pTbl
xor rax, rax
mov byte ptr [rsi+rax+2], 1 ; mark '2' as prime
mov rcx, 3 ; skip '1' and '2' (already marked)
add rax, rcx
@@:
add rax, rcx
cmp rax, arrsize
jae done1
cmp byte ptr [rsi+rax], 0
jz @b
mov byte ptr [rsi+rax], 0
jmp @b
done1:
inc rcx ; increment counter twice
inc rcx ; effectively skipping even numbers
cmp rcx, arrsize
jae done2
xor rax, rax
add rax, rcx
jmp @b
done2:
mov hPrimes, flcreate("Primes.txt")
mov rdi, 2
flprint hPrimes, str$(rdi),lf
mov rdi, 3 ; first odd number afert '2'
@@:
cmp byte ptr [rsi+rdi], 1
jnz noprint
nop
flprint hPrimes, str$(rdi),lf
noprint:
inc rdi ; inc rdi twice, effectively skipping over
inc rdi ; even numbers which are not prime except '2'
cmp rdi, arrsize
jge outtahere
jmp @b
outtahere:
flclose hPrimes
invoke GlobalFree, pTbl
noarray:
invoke ExitProcess, 0
start endp
end
--- End code ---
fibonacci 64 bit is coming soon, adding the finishing touches. :)
Navigation
[0] Message Index
[#] Next page
Go to full version