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 Select Expand

        include \masm64\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


 

[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 Select Expand


        include \masm64\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.....................

[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 Select Expand

        include \masm64\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.

[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 Select Expand

        ; faster 'basic' 64 bit prime sieve
       
        include \masm64\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



fibonacci 64 bit is coming soon, adding the finishing touches.  :)

[mikeburr]

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]

Sorry Arielle64!

Look like JJ is too busy to talk with bots today 

[jj2007]

IMHO SMF should provide a setting that stops people who have not been members for at least n days from embedding links.

[stevenxie]

Hi,0000.It is very good! I am a MASM enthusiast and I should study hard from you

[zedd151]

Attached, original version of primes64
The original file that was linked in the first post was lost and the link no longer worked some time ago...

primes64.asm ; is the original source code for this project. Recreated from the first post here.
makeit.bat ; assembles the file
testprimes.bat ; runs the program and creates a listing of valid primes to maximum -> primes.txt

[zedd151]

Fixed paths to masm64rt.inc in the code in my posts above. Originally masm64 was combined with masm32 in the masm32 directory (per hutch-- back then). Now most members have masm64 in its own directory in the root of the drive that the Masm64 SDK is installed on.   

[six_L]

Hi,zedd151
thanks for sharing.

the maxPrimes of Human being has found: 2^74207281-1
length:22,338,618 bits numbers.

How to determine whether such a large number is prime?

[Gunther]

six_L,

the maxPrimes of Human being has found: 2^74207281-1
length:22,338,618 bits numbers.

as far as I remember correctly with a modified sieve process. Erathosthenes (please note where the h is)
was the name giver for it. Although Wikipedia has a strong BIAS on many topics, these two articles
are halfway usable. I hope this has helped you.

[zedd151]

Eratosthenes via World History Encyclopedia

Sieve of Eratosthenes
An example of this is his algorithm known as the Sieve of Eratosthenes which located prime numbers. A prime number is any natural number that is not reached by combining two smaller numbers while a composite number is the product of any given smaller amounts. The Greeks did not define the number 1 even as a number and so the number 2 was understood as the first prime number. The Sieve of Eratosthenes was so-called because it acted like a sieve to separate prime numbers from composite numbers. Beginning with the number 2, the multiples of composite numbers are sequentially revealed until all that is left in the "sieve" are prime numbers. This innovation assisted in easier and more efficient mathematical calculations.

[six_L]

Hi, Gunther/zedd151

Thanks you for the useful information.