Microsoft MVP성태의 닷넷 이야기
Math: 3. "유클리드 호제법"과 "Bezout's identity" 구현 코드(C#) [링크 복사], [링크+제목 복사],
조회: 29435
글쓴 사람
정성태 (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

비밀번호

댓글 작성자
 




1  2  3  4  5  6  7  8  9  10  [11]  12  13  14  15  ...
NoWriterDateCnt.TitleFile(s)
13704정성태8/2/20249601닷넷: 2290. C# - 간이 dotnet-dump 프로그램 만들기파일 다운로드1
13703정성태8/1/20248156닷넷: 2289. "dotnet-dump ps" 명령어가 닷넷 프로세스를 찾는 방법
13702정성태7/31/20249150닷넷: 2288. Collection 식을 지원하는 사용자 정의 타입을 CollectionBuilder 특성으로 성능 보완파일 다운로드1
13701정성태7/30/20249515닷넷: 2287. C# 13 - (4) Indexer를 이용한 개체 초기화 구문에서 System.Index 연산자 허용파일 다운로드1
13700정성태7/29/20249438디버깅 기술: 200. DLL Export/Import의 Hint 의미
13699정성태7/27/20249483닷넷: 2286. C# 13 - (3) Monitor를 대체할 Lock 타입파일 다운로드1
13698정성태7/27/20249294닷넷: 2285. C# - async 메서드에서의 System.Threading.Lock 잠금 처리파일 다운로드1
13697정성태7/26/20248609닷넷: 2284. C# - async 메서드에서의 lock/Monitor.Enter/Exit 잠금 처리파일 다운로드1
13696정성태7/26/20248333오류 유형: 920. dotnet publish - error NETSDK1047: Assets file '...\obj\project.assets.json' doesn't have a target for '...'
13695정성태7/25/20248631닷넷: 2283. C# - Lock / Wait 상태에서도 STA COM 메서드 호출 처리파일 다운로드1
13694정성태7/25/20248803닷넷: 2282. C# - ASP.NET Core Web App의 Request 용량 상한값 (Kestrel, IIS)
13693정성태7/24/20248009개발 환경 구성: 717. Visual Studio - C# 프로젝트에서 레지스트리에 등록하지 않은 COM 개체 참조 및 사용 방법파일 다운로드1
13692정성태7/24/20249191디버깅 기술: 199. Windbg - 리눅스에서 뜬 닷넷 응용 프로그램 덤프 파일에 포함된 DLL의 Export Directory 탐색
13691정성태7/23/20248186디버깅 기술: 198. Windbg - 스레드의 Win32 Message Queue 정보 조회
13690정성태7/23/20247662오류 유형: 919. Visual C++ 리눅스 프로젝트 - error : ‘u8’ was not declared in this scope
13689정성태7/22/20249909디버깅 기술: 197. Windbg - PE 포맷의 Export Directory 탐색
13688정성태7/21/20248392닷넷: 2281. C# - Lock / Wait 상태에서도 일부 Win32 메시지 처리파일 다운로드1
13687정성태7/19/20249222닷넷: 2280. C# - PostThreadMessage로 보낸 메시지를 Windows Forms에서 수신하는 방법파일 다운로드1
13686정성태7/19/20248879오류 유형: 918. Visual Studio - ATL Simple Object 추가 시 error C2065: 'IDR_...': undeclared identifier
13685정성태7/19/20248728스크립트: 66. Windows 디렉터리 경로를 WSL의 /mnt 포맷으로 구하는 방법 - 두 번째 이야기
13684정성태7/19/20249351닷넷: 2279. C# - 문자열 보간식 사례 (예: 조건 연산자 사용)
13683정성태7/18/20248441오류 유형: 917. ClrMD - Linux 환경의 .NET 5 덤프 분석 시 hang 현상
13682정성태7/18/20248794닷넷: 2278. WPF - 스레드에 종속되는 DependencyObject파일 다운로드1
13681정성태7/17/20248165닷넷: 2277. C# 13 - (2) 메서드 그룹의 자연 타입 개선 (메서드 추론 개선)파일 다운로드1
13680정성태7/16/20249170닷넷: 2276. C# - Method Group, Natural Type, function_type파일 다운로드1
13679정성태7/16/20247560Linux: 76. Linux - C++ (getaddrinfo 등을 담고 있는) libnss 정적 링크
1  2  3  4  5  6  7  8  9  10  [11]  12  13  14  15  ...