Реализация расширенного евклидова алгоритма

Question

Я хочу создать комбинацию функций, которая задает два целых числа n и m, возвращает тройку целых чисел (a, b, gcd (n, m)), такую ​​что: am + bn = gcd (n, m) Не следует предполагать, что целые числа всегда будут положительными.

gcd :: Int -> Int -> Int 
gcd n m 
| n == m = n 
| n > m = gcd (n-m) m 
| n < m = gcd n (m-n) 

combine :: Int ->Int -> (Int,Int,Int) 
x1=1; y1=0; x2=0; y2=1 
while (m /=0) 
( q=div n m ; r=mod n m ; n=m ; m=r 
    t=x2 ; x2=x1-q*x2 ; x1=t 
    t=y2 ; y2=y1-q*y2 ; y1=t ) 
combine n m = (x1,y1,gcd(n,m)) 

Вы найдете ссылку на изображение с экрана. Нажмите на меня --->! [Link] http://prikachi.com/images.php?images/238/8749238o.png Пожалуйста, если у кого-то есть решение и у меня есть идея, что я могу заменить для создания функции, было бы очень признательно. Тест для функции: объединить 3 2 должен дать этот результат => (1, -1,1)

Answer 1

Я думаю, что вы могли бы искать что-то вроде этого:

combine :: Int ->Int -> (Int,Int,Int) 
combine n m = (x1, y1, gcd n m) where 
    (x1, y1) = gcdext n m 

gcdext :: Int -> Int -> (Int, Int) 
gcdext n m = gcdexthelper n m 1 0 0 1 where 
    gcdexthelper n m x1 y1 x2 y2 
    | m == 0 = (x1, y1) 
    | otherwise = gcdexthelper m r x1p y1p x2p y2p where 
    q = div n m 
    r = mod n m 
    x1p = x2 
    y1p = y2 
    x2p = x1 - q * x2 
    y2p = y1 - q * y2 

Вы можете, конечно, реализовать то же самое с циклом while, но я считаю, что рекурсия в Haskell намного читаема, поэтому я использовал ее здесь.

И, кстати, GCD является стандартной библиотечной функцией в Haskell, поэтому вам не нужно писать свои собственные.