实现扩展的欧几里得算法 [英] Implementing Extended Euclidean algorithm

问题描述

我想让一个函数组合起来，给定两个整数n和m，返回一个三进制整数 (a，b，gcd(n，m))这样: am + bn = gcd(n，m) 不应该假设整数将始终为正.

I want to make a function combine which given two integers n and m, returns a triple of integers (a, b, gcd(n, m)) such that: am + bn = gcd(n, m) Should not assume that the integers will always be positive.

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

您将找到一个截屏图片链接.请点击我--->！[链接] http://prikachi.com/images .php?images/238/8749238o.png 如果有人有解决方案并且知道我可以替换以创建该功能的想法，将不胜感激. 测试功能:结合3 2应该给出这个结果=>(1，-1,1)

You will find a screen capture picture link. Click me---> ![link] http://prikachi.com/images.php?images/238/8749238o.png Please if someone have a solution and have idea what I could replace to create the function, would be much appreciated. Test for the function: combine 3 2 should give this result => (1,-1,1)

推荐答案

我认为您可能正在寻找这样的东西:

I think you might be looking for something like this:

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中更具可读性，因此我在这里使用了它.

You can of course implement the same with a while loop, but I believe recursion is much more readable in Haskell, so I used it here.

顺便说一句，GCD是Haskell中的标准库函数，因此无需自己编写.

And by the way, GCD is a standard library function in Haskell, so no need to write your own.

这篇关于实现扩展的欧几里得算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！