Microsoft MVP성태의 닷넷 이야기
Math: 3. "유클리드 호제법"과 "Bezout's identity" 구현 코드(C#) [링크 복사], [링크+제목 복사],
조회: 29658
글쓴 사람
정성태 (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)
10805정성태6/15/201524119Java: 17. 자바의 재미있는 상수 처리 방식
10804정성태6/10/201524127.NET Framework: 514. .NET CLR2 보안 모델에서의 APTCA 역할 (2)파일 다운로드1
10803정성태6/2/201526063.NET Framework: 513. UWP(Universal Windows Platform) 응용 프로그램의 새로운 라이브러리 버전 관리 해법 [2]
10802정성태6/2/201525369개발 환경 구성: 269. 마이크로소프트 온라인 강좌 소개 - Azure VPN 구성 방법 [1]
10801정성태5/31/201530508.NET Framework: 512. async/await 사용 시 hang 문제가 발생하는 경우 - 두 번째 이야기 [3]
10800정성태5/29/201525952개발 환경 구성: 268. 소개 - 프로세싱(https://processing.org/)
10799정성태5/29/201523502사물인터넷: 3. 책 소개 - 라즈베리 파이로 구현하는 사물 인터넷 프로젝트 [1]
10798정성태5/26/201523519기타: 53. 2015년 6월 10일 밤 10시 온라인 세미나 - 새로운 Windows 10 App을 개발하는 방법
10797정성태5/23/201523213VC++: 91. 자식 스레드에 자동 상속되는 TEB의 SubProcessTag 필드파일 다운로드1
10796정성태5/23/201534007오류 유형: 293. SQL Server Management Studio 실행 시 "Cannot find one or more components" 오류
10795정성태5/23/201532157오류 유형: 292. InstallUtil로 .NET 서비스 등록 시 오류 - Operation is not supported. (Exception from HRESULT: 0x80131515). [3]
10794정성태5/22/201527093개발 환경 구성: 267. (무료) 마이크로소프트 온라인 강좌 소개 - 네트워킹 기초 [1]
2925정성태5/14/201526433디버깅 기술: 73. PDB 기호 파일의 경로 구성 방식파일 다운로드1
2924정성태5/14/201529870VS.NET IDE: 100. 비주얼 스튜디오 원격 디버깅 시 'Unknown function' 콜스택이 나온다면?
2923정성태5/12/201589271기타: 52. 도서: 시작하세요! C# 6.0 프로그래밍: 기본 문법부터 실전 예제까지 [17]
2922정성태5/12/201525578오류 유형: 291. ssindex.cmd 실행 시 '...[tfs_collection_url]...' not found in srcsrv.ini 오류 발생
2921정성태5/9/201532308개발 환경 구성: 266. 인텔에서 구현한 최대 절전 모드 기능 - Intel® Rapid Start Technology
2920정성태5/9/201523221오류 유형: 290. 디스크 관리자의 파티션 축소 시, There is not enough space available on the disk(s) to complete this operation.
2919정성태5/9/201523209오류 유형: 289. Error: this template attempted to load component assembly 'NuGet.VisualStudio.Interop, ...'
2918정성태5/9/201541714Windows: 111. 복구(Recovery) 파티션 삭제하는 방법 [3]
2917정성태5/9/201532368오류 유형: 288. .NET Framework 4.6이 설치된 경우 "Intel® Rapid Storage Technology (Intel® RST) RAID Driver"가 설치 안 되는 문제 [5]
2916정성태5/9/201533389오류 유형: 287. 레지스트리 권한 오류 - Cannot edit [Registry key name]: Error writing the value's new contents.
2915정성태5/9/201532860개발 환경 구성: 265. TrustedInstaller 권한으로 프로그램 실행시키는 방법 [11]
2914정성태5/9/201529899DDK: 7. 정식 인증서가 있는 경우 Device Driver 서명하는 방법 [2]
2913정성태4/30/201527589.NET Framework: 511. Build 2015 행사에서 소개된 (맥/리눅스/윈도우 용 무료) Visual Studio Code 개발 도구 [8]
2912정성태4/29/201523270오류 유형: 286. VirtualBox에 Windows 8/2012 설치 시 "Error Code: 0x000000C4" 오류 발생
... 121  122  123  124  125  [126]  127  128  129  130  131  132  133  134  135  ...