Implémentation d'un algorithme euclidien étendu

Question

Je veux faire une fonction combinant deux entiers n et m, renvoie un triple d'entiers (a, b, gcd (n, m)) tel que: am + bn = gcd (n, m) Ne supposez pas que les entiers seront toujours positifs.

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

Vous trouverez un lien d'image de capture d'écran. Cliquez sur moi --->! [Link] http://prikachi.com/images.php?images/238/8749238o.png S'il vous plaît si quelqu'un a une solution et avoir une idée de ce que je pourrais remplacer pour créer la fonction, serait très apprécié. Test de la fonction: combiner 3 2 devrait donner ce résultat => (1, -1,1)

Answer 1

Je pense que vous cherchez peut-être quelque chose comme ceci:

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 

Vous pouvez bien sûr mettre en œuvre la même chose avec une boucle while, mais je crois que la récursivité est beaucoup plus lisible dans Haskell, donc je l'ai utilisé ici. Et à propos, GCD est une fonction de bibliothèque standard dans Haskell, donc pas besoin d'écrire les vôtres.