Как мне запрограммировать наибольшую распространенную программу делителей 80х86?

Я знаю, что существуют разные методы поиска gcd из двух чисел, но я хочу знать, какие из команд лучше всего заданы на ассемблере, и как мне внедрить этот метод в программу?

Вот что у меня так далеко:

.586
.MODEL FLAT

INCLUDE io.h            ; header file for input/output

.STACK 4096

.DATA
number1 DWORD ?
number2 DWORD ?
prompt1 BYTE "Please enter an integer for X", 0
prompt2 BYTE "Please enter an integer for Y", 0
string BYTE 40 DUP (?)
resultLbl BYTE "The greatest common divisor of X and Y is", 0
gcd BYTE 11 DUP (?), 0

.CODE
_MainProc PROC
    input prompt1, string, 40
    atod string
    mov number1, eax

    input prompt2, string, 40
    atod string
    mov number2, edx

    mov eax, number1
    mov edx, number2

Get_GCD:
    xchg eax,edx
    cmp eax,edx
    jb Get_GCD
    sub eax,edx
    test edx,edx
    jnz Get_GCD
    ret

    dtoa gcd, edx
    output resultLbl, gcd

    mov eax, 0
    mov edx, 0
    ret
_MainProc ENDP
END                             ; end of source code

Я запускаю его, и ничего не происходит.

Источник

3 ответа

Удалите ret, который находится после jnz Get_GCD и перед dtoa. Цикл алгоритма вычитания Евклида может быть сокращен:

;                                       ;eax and edx are the numbers
gcd0:   cmp     edx,eax                 ;edx = smaller number
        jb      gcd1
        xchg    eax,edx
gcd1:   sub     eax,edx                 ;subtract smaller from larger
        jnz     gcd0                    ;loop if not done
;                                       ;edx = gcd

Обратите внимание, что наихудшим случаем для вышеуказанного цикла является eax = 0xffffffff и edx = 1, где для завершения требуется 4 миллиарда циклов. Алгоритм по модулю Евклида, показанный ниже, использует деление, но в наихудшем случае число циклов n равно: n <= 5 log10 (меньшее число) или n <= 1.50515 log2 (меньшее число). Для 32-разрядных целых чисел без знака наихудший случай - это два числа Фибоначчи, 1836311903 и 2971215073 (gcd = 1), где число циклов = 45, что составляет <= 5 log10(1836311903) (~= 46.32).

Метод Евклида по модулю:

;                                       ;eax and ebx are the numbers
        cmp     ebx,eax                 ;ebx = smaller number
        jb      gcd0
        xchg    eax,ebx
gcd0:   xor     edx,edx                 ;divide: larger / smaller
        div     ebx
        mov     eax,ebx                 ;eax = new larger (was smaller)
        mov     ebx,edx                 ;ebx = new smaller (new remainder)
        or      ebx,ebx                 ;loop if new smaller != 0
        jnz     gcd0
;                                       ;eax = gcd
Источник 
include Irvine32.inc

    .data

factor  DWORD 60
i       DWORD 2
largest DWORD ?

str1    BYTE "Greatest common factor",0

    .code 
    main PROC

top:    
    mov eax,factor
    mov ebx,i
    xor edx,edx
    div ebx
    call writedec
    cmp ebx,eax
    je L2
    call crlf
    cmp eax,factor
    jb L1
    inc i
    jmp top
L1:
    mov largest,ebx    
L2:
    mov eax,largest
    mov edx,OFFSET str1
    call writestring
    call writedec

    exit

    main ENDP
    END main
Источник 
Get_GCD:
    xchg EAX,EDX
    cmp EAX,EDX
    jb Get_GCD
    sub EAX,EDX
    test EDX,EDX
    jnz Get_GCD
    ret
Источник
Другие вопросы по тегам