rolisz's site

Project Euler și AC

Pentru că marți am examen practic la Arhi­tec­tura Cal­cu­la­toarelor, 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 al­go­rit­mică, 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 start

Calculul se face corect pentru 1000 (rezultatul este 233168), problema este la afisarea rezul­tat­u­lui 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ă im­ple­mentez algoritmul lui Fourier pentru împărțire în Assembly, așa că testați în Turbo Debugger.

Problem 2: By con­sid­er­ing 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 start

Sper 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.