80x86 어셈블리가 가장 큰 제수 프로그램을 어떻게 프로그램합니까?

Question

두 숫자의 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 

나는 그것을 실행하고 아무 일도 발생하지 않습니다.

Answer 1

Get_GCD: 
    xchg EAX,EDX 
    cmp EAX,EDX 
    jb Get_GCD 
    sub EAX,EDX 
    test EDX,EDX 
    jnz Get_GCD 
    ret 

Answer 2

jnz Get_GCD 이후와 dtoa 앞에있는 ret를 제거하십시오. 유클리드 뺄셈 알고리즘 루프가 단축 될 수 있습니다 위의 루프 최악의 경우는 EAX = 0xffffffff를하고 완료하는 데 40 억 개 루프 소요 EDX = 1이다

;          ;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 

하는 것으로. 유클리드의 모듈로 알고리즘은 나눗셈을 사용하지만 최악의 루프 수는 n < = 5 log10 (더 작은 수) 또는 n < = 1.50515 log2 (더 작은 수)입니다. 32 비트 부호없는 정수의 경우 최악의 경우는 두 개의 피보나치 수 1836311903과 2971215073 (gcd = 1)입니다. 여기에서 루프 수는= 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 

Answer 3

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