Project Euler și AC
Pentru că marți am examen practic la Arhitectura Calculatoarelor, am decis să mă pregătesc și eu un picuț. Seara la 10. Cu ce să ma pregătesc mai bine decât cu probleme de la Project Euler? Acesta este un site unde se găsesc o mulțime de probleme, mai mult de algoritmică, care pot fi rezolvate în orice limbaj de programare. Am făcut primele 3 în PHP mai demult, iar acum o să refac primele 2 în Assembly (cu anumite limitări), și o să încerc să mă explic cât mai bine.
Problema 1: Find the sum of all the multiples of 3 or 5 below 1000.
assume cs:code, ds:data
data segment
suma dd 0; suma sub forma de numar
suma_caract db 10 DUP(?) ; suma sub forma de sir de caractere
citire db 'Dati numarul pana la care sa se mearga $'
maxNrLength db 10 ; lungimea maxima a numarului
nrLength db ? ; lungimea numarului dat de la tastatura
numar_caract db 10 DUP(?) ; numarul dat de la tastatura sub forma de sir de caractere
numar dw 0 ; numarul dat de la tastatura sub forma de numar
sfarsit db 'Suma multiplilor de 3 si 5 este $'
zece dw 10 ; pentru impartire
trei dw 3
cinci dw 5
data ends
code segment
getNumar proc ;transforma sirul de caractere in numar
; punem in cl lungimea sirului de caractere care reprezinta numarul
mov cl,nrLength
mov ch,0
; punem in si offsetul sirului de caractere si setam direction flag la 0
mov si,offset numar_caract
cld
parcurge:
; citim urmatorul caracter si scadem 48 din el pentru a obtine cifra sub forma de numar, inmultim numarul cu 10 si apoi adunam cifra noua
lodsb
sub al,48
mov bl,10
mov dl, al
mov ax, numar
mul bl
mov dh,0
add ax,dx
mov numar, ax
loop parcurge
ret
getNumar endp
getCarac proc; transforma numarul in sir de carac
mov di, offset suma_caract + 10
std
mov al, '$'
stosb
mov bx, word ptr suma + 2; mutam prima parte a numarului in bx pentru a-l transforma
cmp bx,0
je mutapartea2 ; daca prima parte e diferita de 0 trecem la a o transforma in sir de caractere. daca e 0 trecem la a transforma partea a 2a in sir de caractere
impartire:
mov ax,bx
mov dx,0
div zece
mov bx,ax
add dx,48
mov al,dl
stosb
cmp bx,0
jne impartire
mutapartea2:; aceasi chestie doar ca pentru a 2a parte a sirului de caractere
mov bx, word ptr suma
impartire2:
mov ax,bx
mov dx,0
div zece
mov bx,ax
add dx,48
mov al,dl
stosb
cmp bx,0
jne impartire2
ret
getCarac endp
start:
; mutam adresa segmentului data in ds si es
mov ax, data
mov ds, ax
mov es, ax
; afisam mesajul pentru citire
mov ah,09h
mov dx, offset citire
int 21h
; citim numarul maxim
mov ah,0Ah
mov dx, offset maxNrLength
int 21h
call getNumar
;mutam in cx numar - 3 pentru a indica de cate ori vrem sa se repete operatiile
mov cx, numar
sub cx,3
; incepem cautare de la 3
mov bx,3
aduna:
; mutam numarul la care am ajuns in ax si il impartim la 3, respectiv 5 si comparam restul din dx cu 0.
mov ax,bx
mov dx,0
div trei
cmp dx,0
je multiplu
mov ax,bx
mov dx,0
div cinci
cmp dx,0
je multiplu
jne comun
multiplu: ; daca vreunul din resturi e 0 inseamna ca numarul e multiplu de 3 sau 5 si il adunam la prima parte a sumei, iar la a doua adunam eventualul transport (atentie la little endian)
add word ptr suma,bx
adc word ptr suma + 2, 0
comun:
; crestem numarul cu 1
inc bx
loop aduna
call getCarac
; afisam mesajul de sfarsit
mov ah,09h
mov dx, offset sfarsit
int 21h
; afisam suma
mov ah, 09h
mov dx, offset suma_caract
int 21h
; terminam programul si returnam 0
mov ax,4C00h
int 21h
code ends
end startCalculul se face corect pentru 1000 (rezultatul este 233168), problema este la afisarea rezultatului pentru valori ale lui n mai mari de 500. De la acea valoare încolo suma nu se mai poate reprezenta pe 16 biți, iar cum la afișare facem împărțire la 10, apare o problemă la împărțirea unui număr pe 32 biți la 10. Și nu am chef să implementez algoritmul lui Fourier pentru împărțire în Assembly, așa că testați în Turbo Debugger.
Problem 2: By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms. Problemă care se vede din start: trebuie să merg până la 4.000.000, care încape pe 32 de biți. Așa că o să reducem un pic domeniul până la 65000 :D. Dar algoritmul e la fel.
assume cs:code, ds:data
data segment
suma dd 0; suma sub forma de numar
suma_caract db 10 DUP(?) ; suma sub forma de sir de caractere
citire db 'Dati numarul pana la care sa se mearga $'
maxNrLength db 10 ; lungimea maxima a numarului
nrLength db ? ; lungimea numarului dat de la tastatura
numar_caract db 10 DUP(?) ; numarul dat de la tastatura sub forma de sir de caractere
numar dw 0 ; numarul dat de la tastatura sub forma de numar
sfarsit db 'Suma termenilor pari din seria Fibonacci este $'
zece dw 10 ; pentru impartire
f1 dw 1 ; termeni fibonacci
f2 dw 2
data ends
code segment
getNumar proc ;transforma sirul de caractere in numar
; punem in cl lungimea sirului de caractere care reprezinta numarul
mov cl,nrLength
mov ch,0
; punem in si offsetul sirului de caractere si setam direction flag la 0
mov si,offset numar_caract
cld
parcurge:
; citim urmatorul caracter si scadem 48 din el pentru a obtine cifra sub forma de numar, inmultim numarul cu 10 si apoi adunam cifra noua
lodsb
sub al,48
mov bl,10
mov dl, al
mov ax, numar
mul bl
mov dh,0
add ax,dx
mov numar, ax
loop parcurge
ret
getNumar endp
getCarac proc; transforma numarul in sir de carac
mov di, offset suma_caract + 10
std
mov al, '$'
stosb
mov bx, word ptr suma + 2; mutam prima parte a numarului in bx pentru a-l transforma
cmp bx,0
je mutapartea2 ; daca prima parte e diferita de 0 trecem la a o transforma in sir de caractere. daca e 0 trecem la a transforma partea a 2a in sir de caractere
impartire:
mov ax,bx
mov dx,0
div zece
mov bx,ax
add dx,48
mov al,dl
stosb
cmp bx,0
jne impartire
mutapartea2:
mov bx, word ptr suma
impartire2:
mov ax,bx
mov dx,0
div zece
mov bx,ax
add dx,48
mov al,dl
stosb
cmp bx,0
jne impartire2
ret
getCarac endp
start:
; mutam adresa segmentului data in ds si es
mov ax, data
mov ds, ax
mov es, ax
; afisam mesajul pentru citire
mov ah,09h
mov dx, offset citire
int 21h
; citim numarul maxim
mov ah,0Ah
mov dx, offset maxNrLength
int 21h
call getNumar
repeta:
mov ax, f1 ; comparam numarul cu 1 prin AND
test ax,1
je urmator
; daca e 0 inseamna ca e par si il adunam la suma, avand grija la little endianess
mov ax, f1
add word ptr suma, ax
adc word ptr suma + 2, 0
urmator: ; generam urmatorul termen fibonacci, salvand in ax f2, adunand la f2 f1 (prin cx), si mutand in f1 ax (egal cu f2)
mov ax, f2
mov cx, f1
add f2, cx
mov f1, ax
cmp ax, numar ; comparam f1 cu numarul si daca e mai mic repetam
jb repeta
call getCarac
;afisam mesajul de sfarsit
mov ah,09h
mov dx, offset sfarsit
int 21h
; afisam suma
mov ah, 09h
mov dx, offset suma_caract
int 21h
; terminam programul si returnam 0
mov ax,4C00h
int 21h
code ends
end startSper că pe cineva au ajutat aceste două probleme. Și acum să merg să învăț un set de chestii inutile: cum lucrez cu fișiere în ASM pe 16 biți și DOS.
