### Author Topic: Prime sieve 64 bit  (Read 4193 times)

#### 0000

• Member
• Posts: 872
##### 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 »

#### 0000

• Member
• Posts: 872
##### 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.

#### 0000

• Member
• Posts: 872
##### 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...
Little by little, we are getting there.....................

#### 0000

• Member
• Posts: 872
##### 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.

#### 0000

• Member
• Posts: 872
##### Re: Prime sieve 64 bit
« Reply #4 on: August 12, 2018, 01:19:33 PM »
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.  :)

#### mikeburr

• Member
• Posts: 134
##### Re: Prime sieve 64 bit
« Reply #5 on: April 26, 2019, 07:11:53 AM »
zedd
primes are all 6k +/- 1 this is the smallest set that includes all primes .. if you introduce that into your test you will eliminate all multiples of 2 x 3 no need for a bt reg,0 js or whatever you are doing for evens [ multiples of 2] ... there are more sophisticated tests that can ascertain whether a number is prime based on the residues [ whats left over after division ie whats in edx (assumption about your methods) based on the fact that each number in turn **[p-1/2] will result in a residue of +/1  when divided by the number you are trying to assess  eg  so lets suppose you are trying to determine whether 31 is prime  2**15 divided by 31 will result in a remainder of 1 ... 3**15 in a remainder of 30 ... the sequence [starting with 1 ] is 1 1 30 1 1 30 1 1 1 1 30 30 30 1 30 1 30 1 1 1 30 30 30 30 1 30 30 1 30 30  all prime numbers are identifiable this way .. except there are some infrequent interlopers. These are called Carmichael numbers although if you write your program to ascertain primality this way you will find a couple of extras . its fairly obvious why these produce "fake" results.  Now if you are about to complain that raising a number to an enormous power is not viable on your machine then think again as ive just run the 31 analysis and its very quick .. similarly can run a sequence of numbers limited say by an array size in the data section or for the more ambitious Heap storage and either a file output or overlaying the voluminous product onto a window with indexing  [ i used a Bt Tree type of arrangement] .. for a 32 bit system is  about the first 6,500 primes .. for a 64 bit system its a lot 10**13 [ie 13 digits ]requires 233,000 primes ... and 64 bit is 19 digits or thereabouts ... for very large numbers elliptical methods may be used but they are less suitable to your aims  not sure if this helps but if you like a list of the first 233,000 primes i can send that or attach it here possibly ??? its a bit big for that though    regards mike burr

#### HSE

• Member
• Posts: 1765
• <AMD>< 7-32>
##### Re: Prime sieve 64 bit
« Reply #6 on: July 28, 2021, 07:28:31 AM »
Sorry Arielle64!

Look like JJ is too busy to talk with bots today

#### jj2007

• Member
• Posts: 11583
• Assembler is fun ;-)
##### Re: Prime sieve 64 bit
« Reply #7 on: July 28, 2021, 08:30:53 AM »
IMHO SMF should provide a setting that stops people who have not been members for at least n days from embedding links.

#### stevenxie

• Member
• Posts: 54
##### Re: Prime sieve 64 bit
« Reply #8 on: August 08, 2021, 05:42:28 PM »
Hi,0000.It is very good! I am a MASM enthusiast and I should study hard from you