Реализации алгоритмов/Расширенный алгоритм Евклида

Расширенный алгоритм Евклида вычисляет НОД двух заданных целых чисел и их коэффициенты Безу.

На языке Си

#include <stdio.h>
int main(){
    int a, b, p=1, q=0, r=0, s=1, x, y;
    scanf("%d %d",&a,&b);
    while (a && b) {
        if (a>=b) {
            a = a - b; 
            p = p - r; 
            q = q - s; 
        } else
        {
            b = b - a; 
            r = r - p; 
            s = s - q; 
        }
    }
    if (a) {
        x = p;
        y = q;
    }else
    {
        x = r;
        y = s;
    }
    printf("%d %d\n",x,y);
    return 0;
}

На языке Python, итерационная версия

def bezout(a, b):
    '''An implementation of extended Euclidean algorithm.
    Returns integer x, y and gcd(a, b) for Bezout equation:
        ax + by = gcd(a, b).
    '''
    x, xx, y, yy = 1, 0, 0, 1
    while b:
        q = a // b
        a, b = b, a % b
        x, xx = xx, x - xx*q
        y, yy = yy, y - yy*q
    return (x, y, a)

На языке Python, рекурсивная версия

def bezout_recursive(a, b):
    '''A recursive implementation of extended Euclidean algorithm.
    Returns integer x, y and gcd(a, b) for Bezout equation:
        ax + by = gcd(a, b).
    '''
    if not b:
        return (1, 0, a)
    y, x, g = bezout_recursive(b, a % b)
    return (x, y - (a // b) * x, g)

На языке Racket, итеративная версия

(define (bezout-gcd a b)
  ; Переменные на каждом шаге алгоритма:                                       
  ; r-1 - r_{n-1} = a * s + b * t;        
  ; r-2 - r_{n-2} = a * u + b * v.
  (define (step r-2 s t r-1 u v)
    (if (zero? r-1)
        ; Если r-1 = 0, то НОД(a, b) = r-2 и его коэффициенты Безу (КБ) найдены, 
        ; возврат этой тройки
        (values r-2 s t)
        
        ; Иначе, нужно вычислить:                                               
        ;   - следующий остаток r = r-1 - r-2 * q (1);    
        ;   - и КБ для r, по выражению (1) и известным КБ для r-1, r-2.        
        ; На следующем шаге:                                                    
        ;   - r-2 ← r-1 (с коэффициентами u и v),              
        ;   - и r-1 ← r с новыми коэффициентами.
        (let-values (((q r) (quotient/remainder r-2 r-1)))                     
          (step r-1 u v                                   
                r (- s (* q u))                   
                  (- t (* q v))))))
  
  ; На первом шаге алгоритма остатками являются a и b с очевидными начальными   
  ; КБ.
  (step a 1 0        
        b 0 1))