"유클리드 호제법"과 "Bezout's identity" 구현 코드(C#)
유클리드 호제법 (Euclidean algorithm)
; http://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95
위에도 소스 코드가 공개되어 있지만, 워낙에 호제법이 명쾌해서 C# 코드로도 쉽게 옮길 수가 있습니다.
static void Main(string[] args)
{
Console.WriteLine(GetResult(247, 962));
Console.WriteLine(GetResult(963, 247));
}
private static string GetResult(int num1, int num2)
{
int gcd = GetGreatestCommonDivisor(num1, num2);
string numFormatter = "{{{0}, {1}}} == ";
if (gcd == 1)
{
return string.Format(numFormatter + "Relatively Prime", num1, num2);
}
int lcm = num1 * num2 / gcd;
return string.Format(numFormatter + "Greatest Common Divisor = {2}, Least Common Multiple = {3}",
num1, num2, gcd, lcm);
}
static int GetGreatestCommonDivisor(int num1, int num2)
{
if (num1 > num2)
{
return GetGreatestCommonDivisor(num2, num1);
}
int remainder = 0;
do
{
remainder = num2 % num1;
num2 = num1;
num1 = remainder;
} while (remainder != 0); // 호제법 구현 do/while 코드
return num2;
}
/* 재귀 호출을 이용한 호제법
static int GetGreatestCommonDivisor(int num1, int num2)
{
if (num2 == 0)
{
return num1;
}
return GetGreatestCommonDivisor(num2, num1 % num2)
}
*/
사실, 여기까지 할 거면 ^^ 이 글을 쓰지도 않았겠지요.
위의 위키피디아 글에 보면 "호제법의 확장"에 대해서도 이야기하고 있는데, 여기에 그대로 내용을 실어보면 다음과 같습니다.
"
정수 m, n의 최대공약수(Greatest Common Divisor)를 gcd(m,n)와 나타낼 때, 확장된 유클리드 호제법을 이용하여, am + bn = gcd(m,n)의 해가 되는 정수 a, b 짝을 찾아낼 수 있다.(a, b 중 한개는 보통 음수가 된다.) 이 식은 Bezout's identity 라고 한다. 위에서 든 예의 경우,
1071 = 1 * 1029 + 42
1029 = 24 * 42 + 21
42 = 2 * 21
이므로
21 = 1029 - 24 * 42 = 1029 - 24 * (1071 - 1 * 1029) = -24 * 1071 + 25 * 1029
가 된다.
"
즉, 2개의 양수 a, b의 최대 공약수를 d라고 했을 때, d는 적절한 정수 r, s에 의해 "d = ar + bs"로 정리될 수 있다는 것인데요. 약간의 코딩을 추가하면 위의 최종 식을 구할 수도 있겠다는 생각이 들더군요.
이를 위해, 호제법을 구하는 코드에서 "a = bq + r"의 형태를 "r = a - bq"의 형태로 기억하는 구조체를 넣어두었습니다.
do
{
remainder = num2 % num1;
RemainderFormula form = new RemainderFormula();
form.Remainder = remainder;
form.SubtractOperand = num2;
form.MultiplyOperand1 = num1;
form.MultiplyOperand2 = (int)Math.Floor((double)num2 / num1);
forms.Add(form);
num2 = num1;
num1 = remainder;
} while (remainder != 0);
forms.Remove(forms.Last());
forms.Reverse();
그다음, 아래와 같이 "Bezout's identity"를 구하는 코드를 추가했습니다.
Dictionary<int, int> counter = new Dictionary<int, int>();
int multiplier = 0;
foreach (var item in forms)
{
if (counter.ContainsKey(item.SubtractOperand) == false)
{
counter[item.SubtractOperand] = 1 * ((multiplier == 0) ? 1 : multiplier);
}
else
{
counter[item.SubtractOperand]++;
}
if (counter.ContainsKey(item.MultiplyOperand1) == false)
{
counter[item.MultiplyOperand1] = -item.MultiplyOperand2;
}
else
{
counter[item.MultiplyOperand1] += (-item.MultiplyOperand2 * multiplier);
}
multiplier = counter[item.MultiplyOperand1];
}
sb.AppendLine(string.Format("\t\t{0} = {1}r + {2}s, when r == {3}, s == {4}",
gcd, num1, num2, counter[num1], counter[num2]));
몇 가지 수를 가지고 테스트 해보니 ^^ 아래와 같이 결과가 잘 나오는 군요.
{247, 962} == Greatest Common Divisor = 13, Least Common Multiple = 18278
13 = 247r + 962s, when r == -35, s == 9
{45, 126} == Greatest Common Divisor = 9, Least Common Multiple = 630
9 = 45r + 126s, when r == 3, s == -1
{255, 315} == Greatest Common Divisor = 15, Least Common Multiple = 5355
15 = 255r + 315s, when r == 5, s == -4
{288, 639} == Greatest Common Divisor = 9, Least Common Multiple = 20448
9 = 288r + 639s, when r == 20, s == -9
{963, 247} == Relatively Prime
참고로, 위키피디아에 "Extended Euclidean algorithm"라고 해서 알고리즘 설명이 나오기는 하는데... 음... 제가 한 방식과는 다르군요.
function extended_gcd(a, b)
x := 0 lastx := 1
y := 1 lasty := 0
while b ≠ 0
quotient := a div b
(a, b) := (b, a mod b)
(x, lastx) := (lastx - quotient*x, x)
(y, lasty) := (lasty - quotient*y, y)
return (lastx, lasty)
이를 C# 코드로 옮겨 보면 다음과 같습니다.
var tuple = GetExtendedGcd(num1, num2);
sb.AppendLine(string.Format("Extended Euclidean algorithm: r == {0}, s == {1}",
tuple.Item2, tuple.Item1));
private static Tuple<int, int> GetExtendedGcd(int num1, int num2)
{
if (num2 > num1)
{
return GetExtendedGcd(num2, num1);
}
int x = 0;
int lastx = 1;
int y = 1;
int lasty = 0;
int quotient = 0;
int tempNum2, tempx, tempy;
while (num2 != 0)
{
quotient = (int)Math.Floor((double)num1 / num2);
tempNum2 = num2;
num2 = num1 % num2;
num1 = tempNum2;
tempx = lastx - quotient * x;
lastx = x;
x = tempx;
tempy = lasty - quotient * y;
lasty = y;
y = tempy;
}
return new Tuple<int,int>(lastx, lasty);
}
역시 머리 좋은 사람들은 다르군요. 동일한 결과를 내면서도 ^^ 제 것보다 더 간결합니다.
{247, 962} == Greatest Common Divisor = 13, Least Common Multiple = 18278
13 = 247r + 962s, Extended Euclidean algorithm: r == -35, s == 9
{45, 126} == Greatest Common Divisor = 9, Least Common Multiple = 630
9 = 45r + 126s, Extended Euclidean algorithm: r == 3, s == -1
{255, 315} == Greatest Common Divisor = 15, Least Common Multiple = 5355
15 = 255r + 315s, Extended Euclidean algorithm: r == 5, s == -4
{288, 639} == Greatest Common Divisor = 9, Least Common Multiple = 20448
9 = 288r + 639s, Extended Euclidean algorithm: r == 20, s == -9
첨부된 파일은 위의 코드를 포함한 예제 프로젝트입니다.
[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]