Author Topic: Prime sieve 64 bit  (Read 357 times)

zedd151

  • Member
  • ****
  • Posts: 847
Prime sieve 64 bit
« on: August 11, 2018, 07:30:19 PM »
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: [Select]
        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

zedds 64 bit prime sieve version 0.001    8)
To assemble, run make64.bat -- to run the program, run run64.bat. The program will run and exit, if ran directly. Unless from a command prompt.
 
« Last Edit: August 11, 2018, 08:31:44 PM by zedd151 »
I'm not always the sharpest knife in the drawer, but I have my moments.  :P

zedd151

  • Member
  • ****
  • Posts: 847
Re: Prime sieve 64 bit
« Reply #1 on: August 11, 2018, 08:07:08 PM »
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: [Select]


        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

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.
I'm not always the sharpest knife in the drawer, but I have my moments.  :P

zedd151

  • Member
  • ****
  • Posts: 847
Re: Prime sieve 64 bit
« Reply #2 on: August 11, 2018, 09:48:51 PM »
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: [Select]

        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
Next step will be to skip iterating through the even numbers during the print operations...  :biggrin:
Little by little, we are getting there.....................
I'm not always the sharpest knife in the drawer, but I have my moments.  :P

zedd151

  • Member
  • ****
  • Posts: 847
Re: Prime sieve 64 bit
« Reply #3 on: August 11, 2018, 10:13:19 PM »
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: [Select]
        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


edit = removed two unnecessary lines of code.
I'm not always the sharpest knife in the drawer, but I have my moments.  :P

zedd151

  • Member
  • ****
  • Posts: 847
Re: Prime sieve 64 bit
« Reply #4 on: August 12, 2018, 01:19:33 PM »
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: [Select]
        ; 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
Download link:  Primes 64 - write file

fibonacci 64 bit is coming soon, adding the finishing touches.  :)
I'm not always the sharpest knife in the drawer, but I have my moments.  :P