Hello, this assingment is for my intro Assembly Language class. Great Common Div

Question

Hello, this assingment is for my intro Assembly Language class.

Great Common Divisor

Write a recursive implemantation of Euclid's algorithm for finding the greatest common divisor (GCD) of two integers. Descriptions of this algorithm are available in algebra books and on the Web. (Note: A nonrecursive version of the GCD problem was given in the programming exercises for Chapter 7.) Write a test program that calls your GCD procedure five times, using the following pairs of integers: (5,20), (24,18), (11,7), (432,226), (26,13). After each procedure call, display the GCD.

Thank you for the help in advance!!!

Explanation / Answer

To get a clearer understanding of Euclid's Algorithm applied let us take a look parts of the program in high level language.

The gcd() function can be written as :

unsigned gcd(unsigned a, unsigned b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a%b);
}

which explains if 'b' becomes 0 then the value of 'a' is returned, otherwise the value of b is returned using "a%b".

The main program will include a standard input output header and the standard library. The rest of the main program will be more or less like :

unsigned gcd(unsigned, unsigned);

int main(int argc, char *argv[])
{
    unsigned a, b;
    if (argc != 3) {
        fprintf(stderr,
                "usage: %s {integer} {integer} ",
                argv[0]);
        return 1;
    }
    a = atoi(argv[1]);
    b = atoi(argv[2]);
    printf("GCD(%u, %u) is %u ", a, b, gcd(a,b));
    return 0;
}

Now that we have a pretty clear understanding of the algorithm in high level language, all we have to do is implement the same for the Assembly level language.

Firstly we code the first block of code that corresponds to the gcd() coded in c :

_gcd:
    push ebp
    mov ebp, esp

    cmp dword [ebp+12], 0
    je .BaseCase

and the rest of the code :

.recurse:
    mov eax, [ebp+8]  
    xor edx, edx      
    div dword [ebp+12]
    push edx          
    mov eax, [ebp+12]
    push eax          
    call _gcd         
    leave     
    ret

.BaseCase:
    mov eax, [ebp+8]
.done:
    leave
    ret

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.