CODEWITHSUNDEEP
assemblyx86greatest-common-divisor
Lorenzo Massone
Lorenzo Massone

Reputation: 19

Finding GCD of an array of n numbers in assembly without external variables

I've got a homework about finding GCD of an array of n numbers in assembly (I'm using asm in Visual Studio 2017) without using external variables in C. The only variable I've got is the length of the array of n numbers. I've got no problem in finding the GCD of the first two numbers of the array but I'm not sure about the way to make a loop where I constantly update my registers with the next number of the array since GCD of 3 numbers a,b,c is GCD(GCD(a,b),c). I'm hopeful about some help.

#include <stdio.h>

void main()
{
    unsigned int intArray[] = {12,24,3};
    int num = sizeof(intArray) / sizeof(intArray[0]);
    unsigned int MCD;

    __asm
    {
        xor ebx,ebx
        xor edx,edx
        xor eax,eax
        mov eax, intArray[0]
        mov ebx, intArray[1]
        jmp major

    zerob:
        mov MCD, eax
        jmp fine

    major:
        cmp eax,ebx
        jg nextstep
        xchg eax,ebx
        jmp major

    nextstep:
        cmp ebx,0
        je zerob
        jne modulus

    modulus:
        div ebx
        mov MCD,edx
        mov eax,ebx
        mov ebx,MCD
        jmp nextstep

    fine:

    }

    printf("M.C.D.: %d \n", MCD);
    getchar();
}

Upvotes: 1

Views: 512

Answers (1)

Fifoernik
Fifoernik

Reputation: 9899

Step 1, cleanup and corrections

Removing redundant instructions, re-arrangeing the code for less jumping, removing the potential infinite loop if 2 identical numbers are used and zeroing EDX before each division:

    mov  eax, intArray[0]
    mov  ebx, intArray[1]

major:
    cmp  eax, ebx
    jg   nextstep
    xchg eax, ebx
nextstep:
    cmp  ebx, 0
    je   zerob
modulus:
    xor  edx, edx
    div  ebx
    mov  eax, ebx
    mov  ebx, edx
    jmp  nextstep

zerob:
    mov  MCD, eax
fine:

Step 2, create loop

Using the number of elements in num, fetching the numbers via a pointer in ESI and turning the inner loop into a DO-WHILE loop (conditionally jumping to the top):

    mov  ecx, num       ;Number of elements
    lea  esi, intArray[0]
    lodsd               ;First number in array
    dec  ecx
    jz   DONE

AGAIN:
    mov  ebx, [esi]     ;Next number in array
    add  esi, 4

major:
    cmp  eax, ebx
    jg   nextstep
    xchg eax, ebx
    jmp  nextstep
modulus:                ;Inner loop
    xor  edx, edx
    div  ebx
    mov  eax, ebx
    mov  ebx, edx
nextstep:
    test ebx, ebx
    jnz  modulus

    dec  ecx
    jnz  AGAIN

DONE:
    mov  MCD, eax
fine:

Upvotes: 2

Related Questions