Реально быстрый алгоритм вычисления НОД

; (c) 2018 by Jin X
; Return GCD of val1 and val2 in EAX (binary algorithm, no recursion calls)
; val1 and val2 are treated as unsigned
proc    FastGCD uses ebx esi edi, val1, val2
        mov     edx,[val2]
        mov     eax,[val1]
 
        test    edx,edx
        jz      .val1noshift            ; if val2 = 0 return val1
        xor     ebx,ebx                 ; bl = left shift count before return (result must be multiplied by 2^bl)
        test    eax,eax
        jz      .val2                   ; if val1 = 0 return val2
 
    .next:
        bsf     esi,eax                 ; esi = count of lower zero bits in val1
        bsf     edi,edx                 ; edi = count of lower zero bits in val2
 
        mov     ecx,esi
        shr     eax,cl                  ; shift val1 right until it will be odd
        mov     ecx,edi
        shr     edx,cl                  ; shift val2 right until it will be odd
 
        cmp     esi,edi
        cmova   esi,edi                 ; esi = min(esi,edi)
        add     ebx,esi                 ; add this number to ebx (bl)
 
        cmp     eax,1
        je      .val1                   ; if val1 = 1 return 1 (val1)
        cmp     edx,1
        je      .val2                   ; if val2 = 1 return 1 (val2)
        cmp     eax,edx
        je      .val1                   ; if val1 = val2 return val1
 
        mov     ecx,eax
        cmovb   eax,edx
        cmovb   edx,ecx                 ; swap val1 and val2 if val1 < val2
        sub     eax,edx
        shr     eax,1                   ; val1 = (val1-val2)/2
        jmp     .next                   ; go to next iteration
 
    .val2:
        mov     eax,edx                 ; eax = val2
    .val1:
        mov     ecx,ebx
        shl     eax,cl                  ; multiple result (eax) by 2^bl
    .val1noshift:
        ret
endp

; (c) 2018 by Jin X
; Return GCD of val1 and val2 in EAX (Euclid algorithm, no recursion calls)
; val1 and val2 are treated as unsigned
proc    EuclidGCD val1, val2
        mov     eax,[val1]
        mov     ecx,[val2]
    @@: jecxz   @F                      ; return val1 if val2 = 0
        xor     edx,edx
        div     ecx                     ; eax = val1 / val2; edx = val1 % val2 (replace this instruction by 'idiv' and previous one by 'cdq' to treat val1 and val2 as signed)
        mov     eax,ecx                 ; eax = val2
        mov     ecx,edx                 ; ecx = edx = val1 % val2
        jmp     @B
    @@: ret
endp

        mov     eax,[val2]
        cdq
        xor     eax,edx
        sub     eax,edx                 ; eax = abs(eax)
        mov     ecx,eax
 
        xor     ebx,ebx                 ; bl = left shift count before return (result must be multiplied by 2^bl)
        mov     eax,[val1]
        cdq
        xor     eax,edx
        sub     eax,edx                 ; eax = abs(eax) = |val1|
        mov     edx,ecx                 ; edx = |val2|
        jz      .val2                   ; if val1 = 0 return |val2|
 
        test    edx,edx
        jz      .val1noshift            ; if val2 = 0 return |val1|