Microsoft MVP성태의 닷넷 이야기
Math: 3. "유클리드 호제법"과 "Bezout's identity" 구현 코드(C#) [링크 복사], [링크+제목 복사],
조회: 30222
글쓴 사람
정성태 (techsharer at outlook.com)
홈페이지
첨부 파일
(연관된 글이 2개 있습니다.)

"유클리드 호제법"과 "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

첨부된 파일은 위의 코드를 포함한 예제 프로젝트입니다.




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

[연관 글]






[최초 등록일: ]
[최종 수정일: 9/15/2021]

Creative Commons License
이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.
by SeongTae Jeong, mailto:techsharer at outlook.com

비밀번호

댓글 작성자
 




... 121  122  123  124  125  126  127  128  129  130  131  132  133  134  [135]  ...
NoWriterDateCnt.TitleFile(s)
1719정성태7/22/201427739Math: 13. 동전을 여러 더미로 나누는 경우의 수 세기(Partition Number) - 두 번째 이야기파일 다운로드1
1718정성태7/19/201437260Math: 12. HTML에서 수학 관련 기호/수식을 표현하기 위한 방법 - MathJax.js [4]
1716정성태7/17/201436905개발 환경 구성: 231. PC 용 무료 안드로이드 에뮬레이터 - genymotion
1715정성태7/13/201431859기타: 47. 운영체제 종료 후에도 USB 외장 하드의 전원이 꺼지지 않는 경우 [3]
1714정성태7/11/201421746VS.NET IDE: 92. Visual Studio 2013을 지원하는 IL Support 확장 도구
1713정성태7/11/201445587Windows: 98. 윈도우 시스템 디스크 용량 확보를 위한 "Package Cache" 폴더 이동 [1]
1712정성태7/10/201434214.NET Framework: 450. 영문 윈도우에서 C# 콘솔 프로그램의 유니코드 출력 방법 [3]
1711정성태7/10/201439082Windows: 97. cmd.exe 창에서 사용할 폰트를 추가하는 방법 [1]
1710정성태7/8/201431827개발 환경 구성: 230. 유니코드의 Surrogate Pair, Supplementary Characters가 뭘까요?파일 다운로드2
1709정성태7/8/201428423VS.NET IDE: 91. Visual Studio에서 32/64비트 IIS Express 실행하는 방법
1708정성태7/7/201425766VS.NET IDE: 90. Visual Studio - 사용자 정의 정적 분석 규칙 만드는 방법 [3]파일 다운로드1
1707정성태7/4/201423858.NET Framework: 449. C#에서 C++로 VARIANT 넘겨주는 방법파일 다운로드1
1706정성태7/3/201422243.NET Framework: 448. .NET SmartClient 컨트롤을 윈도우 8/2012에서 활성화하는 방법파일 다운로드1
1705정성태7/2/201437091VC++: 78. 보이어-무어(Boyer-Moore) 알고리즘이 정말 빠를까? [6]파일 다운로드1
1704정성태7/2/201423438.NET Framework: 447. w3wp.exe AppPool 재생(recycle)하는 방법 정리
1703정성태7/2/201424198.NET Framework: 446. Assembly.Load를 이용해 GAC에 등록된 어셈블리를 로드하는 방법 [1]파일 다운로드1
1702정성태6/23/201424187Phone: 11. Xamarin.Forms - 2. XAML을 이용한 페이지 개발파일 다운로드1
1701정성태6/23/201436525개발 환경 구성: 229. .NET Reflector + Reflexil 도구를 이용해 DLL 코드 변경 [4]
1700정성태6/23/201422976VS.NET IDE: 89. Visual Studio에서 기본 제공되는 성능 프로파일 [2]
1699정성태6/22/201425069Phone: 10. Xamarin.Forms - 1. Forms 시작하기 [2]파일 다운로드1
1698정성태6/22/201426915.NET Framework: 445. [부연 설명] 쉬운 C# 코드를 어럽게 이해하기 [2]
1697정성태6/22/201422696VS.NET IDE: 88. Visual Studio에서 직접 컴파일하는 IL 언어 확장 도구 - IL Support
1696정성태6/22/201422072.NET Framework: 444. clojure와 C#을 통해 이해하는 Sequence와 Vector 형식의 차이점 [1]
1695정성태6/21/201421157개발 환경 구성: 228. PowerShell ISE에서 (입력 기능이 있는) 콘솔 응용 프로그램을 시작하는 방법
1694정성태6/21/201422939개발 환경 구성: 227. 닷넷 용 ClojureCLR 개발환경 설정
1693정성태6/20/201423510개발 환경 구성: 226. Clojure 언어의 윈도우 개발환경 설정
... 121  122  123  124  125  126  127  128  129  130  131  132  133  134  [135]  ...