Author Topic: A little program to seek and write primes, with hardcoded maximum  (Read 8703 times)

Offline andyz74

  • Jr. Member
  • *
  • Posts: 15
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




Offline andyz74

  • Jr. Member
  • *
  • Posts: 15
Re: A little program to seek and write primes, with hardcoded maximum
« Reply #1 on: November 09, 2023, 01:37:37 PM »
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