A little program to seek and write primes, with hardcoded maximum

[andyz74]

Hi there !

Nothing special here, but I thought, maybe somebody is interested in such stuff.
A little program, which seeks and prints out primes until a maximum number (hardcoded in source).

Please don't blame me for parts of documentation is in german; I am not that good in english to translate all correct. ;-)

Done in Debian Linux, 64 bit.

Code: [Select]


; 64-bit  ... gibt Primzahlen aus
; by myself
; nasm -f elf64 primzahlen03.asm
; ld -s -o primzahlen03 primzahlen03.o
; time : 0,15 sec   (Optimierung : prüft nur von 1 bis Wurzel(zu überprüfende Zahl)
; Notiz : Wurzel nicht sehr schnell berechnet.


[bits 64]

; here just variables ---------------------------------------

SECTION .data

para_b db 0
para_w dq 0
primzahl_boolean db 0
ziffer db 0
zahl dd 0
crlf db 13,10


global _start ; global entry point export for ld

SECTION .text

_start:
jmp start2

get_wu: ; seeks iterative for squareroot of testing number...
; could be made way better, if I knew how...

push rax
push rdi
mov rax, [para_w]
mov rdi, rax ; rdi holds number
mov ebx, 0
nochzuklein:
inc ebx
mov eax, ebx
mul eax
cmp rdi, rax ; rechnet : zahl - (eax * eax) // solange größer 0, Wurzel noch nicht erreicht.
jns  nochzuklein
pop rdi
pop rax
ret



check_prim:
push rax
push rdx
push rsi
push rdi
mov byte [primzahl_boolean], 0 ; just a boolean-Variable...
mov rsi, [para_w] ; the number to check
call get_wu
mov rdi, rbx
nochmal:
mov rax,rsi
dec rdi
cmp rdi,1     
je ende
xor rdx, rdx
div rdi
cmp rdx,0
jnz nochmal
mov byte [primzahl_boolean], 1
ende:
pop rdi
pop rsi
pop rdx
pop rax
ret




zeilensprung:
push rax
push rbx
push rcx
push rdx
push rsi
push rdi
mov rax, 4
mov rbx, 1
mov rcx, crlf
mov rdx, 2
int 128
pop rdi
pop rsi
pop rdx
pop rcx
pop rbx
pop rax
ret



print_dez:
push rax
push rbx
push rcx
push rdx
push rsi
push rdi
mov rax, [para_w]
xor rcx,rcx
mov rbx,10

schl1:
xor rdx,rdx
div rbx
push rdx
inc rcx
cmp rax,0

jnz schl1

schl2:
pop rdx
add dl,30h
mov [ziffer],dl
push rcx
mov rax, 4
mov rbx, 1
mov rcx, ziffer
mov rdx, 1
int 128
pop rcx
loop schl2

pop rdi
pop rsi
pop rdx
pop rcx
pop rbx
pop rax
ret






start2:   ; here starts the proggi

mov rcx,200001   ; Number to start. hardcoded.

decrease_further:
mov [para_w], rcx
call check_prim

cmp byte [primzahl_boolean], 1     ; Prime ?
je no_prime

; mov [para_w], rcx
call print_dez

call zeilensprung

no_prime:       ; no prime !
sub rcx, 2
cmp rcx,1
jnz decrease_further


mov rax,1
int 128





[andyz74]

This one does the same, but sets up an array for the primes, which can be used to divide thru. So, only the necessary divisions will be made, what saves time.

Code: [Select]

; 64-bit  ... gibt Primzahlen aus
; by myself
; nasm -f elf64 primzahlen05.asm
; ld -s -o primzahlen05 primzahlen05.o
; time :   0,303 sec (Optimierung : prüft nur von 1 bis Wurzel(zu überprüfende Zahl)
; nur noch durch primzahlen teilen, daher array einführen...
; Notiz : Wurzel ab 04 mit FPU, vllt besser...


[bits 64]

; here just variables ---------------------------------------

SECTION .data

para_b db 0
para_w dq 0
primzahl_boolean db 0
ziffer db 0
zahl dd 0
crlf db 13,10


section .bss
      res :  resq 1     ;reserve 1 quad word for result
 p_array  :  resq 18000
 p_index  :  resq 1
 
global _start ; global entry point export for ld

SECTION .text

_start:
jmp start2


zeige_tabelle: ; wenn Primzahl, dann im Array abspeichern ...
push rax ; ... wir machen naemlich eine Liste.
push rsi
mov rsi, 0
again:
inc rsi
mov rax, 0
call print_dez
mov rax, qword [p_array+rsi*8]
call print_dez
cmp rsi, qword [p_index]
jle again
call zeilensprung
pop rsi
pop rax
ret


add_array: ; wenn Primzahl, dann im Array abspeichern ...
push rax ; ... wir machen naemlich eine Liste.
nop
nop
nop
nop
cmp rsi, 11
jbe toosmallfortable
mov rax, qword [p_index] 
inc rax ; Max-Index der Liste erhöhen
mov qword [p_index], rax
mov qword [p_array+rax*8], rsi ; und am Array-Ende die neue Primzahl anheften. RSI
toosmallfortable:
pop rax
ret


get_wu: ; berechnet die Wurzel der zu untersuchenden Zahl,
fild qword [para_w] ; um nicht unnötig viele Tests zu haben.
fsqrt
fisttp qword [res]
mov rbx, [res]
inc rbx
ret

get_index_of_array:
push rax
mov rax, 0
index_erhoehen:
inc rax
cmp qword [p_array+rax*8], rbx
jl index_erhoehen
mov r15, rax
pop rax
ret


check_prim:
push rax
push rdx
push rsi
push rdi
mov byte [primzahl_boolean], 0 ; just a boolean-Variable... "ist nicht prim"
mov rax, [para_w] ; the number to check
mov rsi, [para_w] ; the number to check
call get_wu ; bringt in rbx die Wurzel von para_w+1
call get_index_of_array ; bringt in r15 den Index im Array, von welchem aus runterwärts verglichen werden muss
nochmal:
mov rdi, qword [p_array+r15*8]
mov rax, rsi
dec r15
cmp r15,0 ; war zuerst 1   
je ende
xor rdx, rdx
div rdi ; teilt rax / rdi
cmp rdx,0
jnz nochmal ; solange noch prim, nach oben, weiter testen
mov byte [primzahl_boolean], 1
ende:
pop rdi
pop rsi
pop rdx
pop rax
ret




zeilensprung:
push rax
push rbx
push rcx
push rdx
push rsi
push rdi
mov rax, 4
mov rbx, 1
mov rcx, crlf
mov rdx, 2
int 128
pop rdi
pop rsi
pop rdx
pop rcx
pop rbx
pop rax
ret



print_dez:
push rax
push rbx
push rcx
push rdx

;mov rax, [para_w]
xor rcx,rcx
mov rbx,10

schl1:
xor rdx,rdx
div rbx
push rdx
inc rcx
cmp rax,0

jnz schl1

schl2:
pop rdx
add dl,30h
mov [ziffer],dl
push rcx
mov rax, 4
mov rbx, 1
mov rcx, ziffer
mov rdx, 1
int 128
pop rcx
loop schl2

pop rdx
pop rcx
pop rbx
pop rax
ret






start2:   ; here starts the proggi

mov rcx,3   ; Number to start. hardcoded.

mov rax, 1
mov qword [rax*8+p_array], 2

mov rax, 2
mov qword [rax*8+p_array], 2

mov rax, 3
mov qword [rax*8+p_array], 3

mov rax, 4
mov qword [rax*8+p_array], 5

mov rax, 5
mov qword [rax*8+p_array], 7

mov rax, 6
mov qword [rax*8+p_array], 11
mov qword [p_index], rax


increase_further:
mov [para_w], rcx
call check_prim

cmp byte [primzahl_boolean], 1     ; Prime ?
je no_prime
mov rsi, [para_w]
call add_array
mov rax, [para_w]
call print_dez

call zeilensprung

;call zeige_tabelle     ; zum debuggen

no_prime:       ; no prime !
add rcx, 2
cmp rcx,200001 ; eigentlich 200001
jbe increase_further


mov rax,1
int 128






[andyz74]

Also for this topic, there's one variant to seek primes by the "Sieve of Eratosthenes".
Seems to be faster as the other ones, but here, we have huge max-values until 2.100.000.000 hardcoded. You may make this smaller for testing.

Code: [Select]

; 64-bit  ... gibt Primzahlen aus, Sieb des Eratosthenes
; by myself
; nasm -f elf64 primzahlen_sieve_buf_opt.asm
; ld -s -o primzahlen_sieve_buf_opt primzahlen_sieve_buf_opt.o
; time :    sec


[bits 64]

; here just variables ---------------------------------------

SECTION .data


ziffer db 0
zahl db  '0000000000'
crlf db 13,10
msg1 db 'Bitte Geduld! Suche Primzahlen zwischen '
msgl1 db 40
msg2 db 'und '
msgl2 db 4
max dq 2100000000     ; 2,1 Milliarden (Max-Value, we seek primes to)
wmin dq 2099990000 ; This is, where we start to print primes)
;  printing all primes will take long time, therefor the above


section .bss
   
 p_array  :  resb 5400000000 ; 5,4 Milliarden
 
global _start ; global entry point export for ld

SECTION .text

_start:
jmp start2


all_be_primes:
xor r8, r8
weiter:
mov byte [p_array+r8], 1    ; wenn 1, dann prim
inc r8
cmp r8, [max]
jne weiter
ret



make_sieve: ; reminder r8 bis r15 als Register
mov r8, 1    ; das zum durchmultiplizieren.
weiter3:
inc r8
cmp byte [p_array+r8], 1 ; nur Primzahlen weiter multiplizieren! Opt!
jne weiter3
mov r9, r8
weiter2:
add r9, r8
mov byte [p_array+r9], 0        ; wenn 0, dann NICHT prim
cmp r9, [max]
jb weiter2 ; unsigned <
inc r8
cmp r8, [max]
jb weiter3 ; unsigned <
ret



print_dez: ; zahl muss in rax sein.
push rax
push rbx
push rcx
push rdx

xor rcx,rcx
mov rbx,10

schl1:
xor rdx,rdx
div rbx
push rdx
inc rcx
cmp rax,0

jnz schl1

xor r8,r8
schl2:
pop rdx
add dl,30h
mov [zahl+r8],dl
inc r8
loop schl2

mov rax, 1 ; Funktionsnummer : schreiben
mov rdi, 1 ; auf STDOUT
mov rsi, zahl ; was schreiben wir
mov rdx, r8 ; wieviel Zeichen
syscall

mov rax, 1 ; Funktionsnummer : schreiben
mov rdi, 1 ; auf STDOUT
mov rsi, crlf ; was schreiben wir
mov rdx, 2 ; wieviele Zeichen
syscall

pop rdx
pop rcx
pop rbx
pop rax
ret


print_info:
mov rax, 1 ; sys_write
mov rdi, 1 ; stdout
mov rsi, msg1 ; message address
mov rdx, 40 ; msgl1 ; message string length
syscall
mov rax, 1 ; Funktionsnummer : schreiben
mov rdi, 1 ; auf STDOUT
mov rsi, crlf ; was schreiben wir
mov rdx, 2 ; wieviele Zeichen
syscall

mov rax, [wmin]
call print_dez

mov rax, 1 ; sys_write
mov rdi, 1 ; stdout
mov rsi, msg2 ; message address
mov rdx, 4  ;msgl2 ; message string length
syscall
mov rax, 1 ; Funktionsnummer : schreiben
mov rdi, 1 ; auf STDOUT
mov rsi, crlf ; was schreiben wir
mov rdx, 2 ; wieviele Zeichen
syscall

mov rax, [max]
call print_dez

ret




start2:   ; here starts the proggi

call print_info

call all_be_primes

call make_sieve

;  mov byte [p_array+27], 1    ; nur zum testen

mov rax, 0
weiter4:
inc rax
cmp rax, [wmin]
jb weiter4
cmp rax, [max]
ja weiter5
cmp byte [p_array+rax], 1
jne weiter4
call print_dez
cmp rax, [max]
jb weiter4 ; unsigned <
weiter5:



mov rax,60
syscall