J & J - 정성태의 닷넷 이야기

사용자

메뉴

최근 덧글

[손민수 (Keystroke)] 괜히 듀얼채널 구성할 때 한번에 같은 제품 사라고 하는 것이 아...[정성태] 전각(Full-width)/반각(Half-width) 기능을 토...[정성태] Vector에 대한 내용은 없습니다. Vector가 닷넷 BCL...[orion] 글 읽고 찾아보니 디자인 타임에는 InitializeCompon...[orion] 연휴 전에 재현 프로젝트 올리자 생각해 놓고 여의치 않아서 못 ...[정성태] 아래의 글에 정리했으니 참고하세요. C# - Typed D...[정성태] 간단한 재현 프로젝트라도 있을까요? 저런 식으로 설명만 해...[정성태] 저도 해 본 것은 아니지만 어차피 in-process로 pyth...[정성태] Full Text Search With ElasticSearch...[정성태] When I define a window class with n...

글쓰기

제목

이름

암호

전자우편

HTML

홈페이지

유형

내용

<div style='display: inline'>
<h1 style='font-family: Malgun Gothic, Consolas; font-size: 20pt; color: #006699; text-align: center; font-weight: bold'>"유클리드 호제법"과 "Bezout's identity" 구현 코드(C#)</h1>

 
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
유클리드 호제법 (Euclidean algorithm)
; <a target='tab' href='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'>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</a>
</pre>
 
위에도 소스 코드가 공개되어 있지만, 워낙에 호제법이 명쾌해서 C# 코드로도 쉽게 옮길 수가 있습니다. 
 
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
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 &gt; 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)
}
*/
</pre>
 
사실, 여기까지 할 거면 ^^ 이 글을 쓰지도 않았겠지요. 
 
위의 위키피디아 글에 보면 "호제법의 확장"에 대해서도 이야기하고 있는데, 여기에 그대로 내용을 실어보면 다음과 같습니다. 
 
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
"
정수 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 
 
가 된다.
"
</pre>
 
즉, 2개의 양수 a, b의 최대 공약수를 d라고 했을 때, d는 적절한 정수 r, s에 의해 "d = ar + bs"로 정리될 수 있다는 것인데요. 약간의 코딩을 추가하면 위의 최종 식을 구할 수도 있겠다는 생각이 들더군요. 
 
이를 위해, 호제법을 구하는 코드에서 "a = bq + r"의 형태를 "r = a - bq"의 형태로 기억하는 구조체를 넣어두었습니다. 
 
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
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();
</pre>
 
그다음, 아래와 같이 "Bezout's identity"를 구하는 코드를 추가했습니다. 
 
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
Dictionary&lt;int, int&gt; counter = new Dictionary&lt;int, int&gt;();

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]));
</pre>
 
몇 가지 수를 가지고 테스트 해보니 ^^ 아래와 같이 결과가 잘 나오는 군요. 
 
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
{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
</pre>
 
참고로, 위키피디아에 "Extended Euclidean algorithm"라고 해서 알고리즘 설명이 나오기는 하는데... 음... 제가 한 방식과는 다르군요. 
 
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
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)
</pre>
 
이를 C# 코드로 옮겨 보면 다음과 같습니다. 
 
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
var tuple = GetExtendedGcd(num1, num2);
sb.AppendLine(string.Format("Extended Euclidean algorithm: r == {0}, s == {1}",
 tuple.Item2, tuple.Item1));

private static Tuple&lt;int, int&gt; GetExtendedGcd(int num1, int num2)
{
    if (num2 &gt; 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&lt;int,int&gt;(lastx, lasty);
}
</pre>
 
역시 머리 좋은 사람들은 다르군요. 동일한 결과를 내면서도 ^^ 제 것보다 더 간결합니다. 
 
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
{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
</pre>
 
<a target='tab' href='http://www.sysnet.pe.kr/bbs/DownloadAttachment.aspx?fid=626&amp;boardid=331301885'>첨부된 파일은 위의 코드를 포함한 예제 프로젝트</a>입니다.

<hr />[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]
</div>

첨부파일

스팸 방지용 인증 번호

1769 (왼쪽의 숫자를 입력해야 합니다.)