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

비밀번호

댓글 작성자
 




... 91  92  93  94  95  96  97  98  99  100  [101]  102  103  104  105  ...
NoWriterDateCnt.TitleFile(s)
11500정성태4/17/201823937개발 환경 구성: 368. PowerShell로 접근하는 Azure의 Access control 보안과 Azure Active Directory의 계정 관리 서비스
11499정성태4/17/201822152개발 환경 구성: 367. Azure - New-AzureRmADServicePrincipal / New-AzureRmRoleAssignment 명령어
11498정성태4/17/201822172개발 환경 구성: 366. Azure Active Directory(Microsoft Enfra ID)의 사용자 유형 구분 - Guest/Member
11497정성태4/17/201819705개발 환경 구성: 365. Azure 리소스의 액세스 제어(Access control) 별로 사용자에게 권한을 할당하는 방법 [2]
11496정성태4/17/201820545개발 환경 구성: 364. Azure Portal에서 구독(Subscriptions) 메뉴가 보이지 않는 경우
11495정성태4/16/201821554개발 환경 구성: 363. Azure의 Access control 보안과 Azure Active Directory의 계정 관리 서비스
11494정성태4/16/201817557개발 환경 구성: 362. Azure Web Apps(App Services)에 사용자 DNS를 지정하는 방법
11493정성태4/16/201819373개발 환경 구성: 361. Azure Web App(App Service)의 HTTP/2 프로토콜 지원
11492정성태4/13/201817777개발 환경 구성: 360. Azure Active Directory의 사용자 도메인 지정 방법
11491정성태4/13/201821078개발 환경 구성: 359. Azure 가상 머신에 Web Application을 배포하는 방법
11490정성태4/12/201819920.NET Framework: 739. .NET Framework 4.7.1의 새 기능 - Configuration builders [1]파일 다운로드1
11489정성태4/12/201817753오류 유형: 463. 윈도우 백업 오류 - a Volume Shadow Copy Service operation failed.
11488정성태4/12/201822254오류 유형: 462. Unhandled Exception in Managed Code Snap-in - FX:{811FD892-5EB4-4E73-A147-F1E079E36C4E}
11487정성태4/12/201819364디버깅 기술: 115. windbg - 닷넷 메모리 덤프에서 정적(static) 필드 값을 조사하는 방법
11486정성태4/11/201818366오류 유형: 461. Error MSB4064 The "ComputeOutputOnly" parameter is not supported by the "VsTsc" task
11485정성태4/11/201827457.NET Framework: 738. C# - Console 프로그램이 Ctrl+C 종료 시점을 감지하는 방법파일 다운로드1
11484정성태4/11/201829074.NET Framework: 737. C# - async를 Task 타입이 아닌 사용자 정의 타입에 적용하는 방법파일 다운로드1
11483정성태4/10/201832610개발 환경 구성: 358. "Let's Encrypt"에서 제공하는 무료 SSL 인증서를 IIS에 적용하는 방법 (2) [1]
11482정성태4/10/201823848VC++: 126. CUDA Core 수를 알아내는 방법
11481정성태4/10/201836693개발 환경 구성: 357. CUDA의 인덱싱 관련 용어 - blockIdx, threadIdx, blockDim, gridDim
11480정성태4/9/201826435.NET Framework: 736. C# - API를 사용해 Azure에 접근하는 방법 [2]파일 다운로드1
11479정성태4/9/201820405.NET Framework: 735. Azure - PowerShell로 Access control(IAM)에 새로운 계정 만드는 방법
11478정성태11/8/201924317디버깅 기술: 115. windbg - 덤프 파일로부터 PID와 환경변수 등의 정보를 구하는 방법 [1]
11477정성태4/8/201820878오류 유형: 460. windbg - sos 명령어 수행 시 c0000006 오류 발생
11476정성태4/8/201822269디버깅 기술: 114. windbg - !threads 출력 결과로부터 닷넷 관리 스레드(System.Threading.Thread) 객체를 구하는 방법
11475정성태3/28/201825986디버깅 기술: 113. windbg - Thread.Suspend 호출 시 응용 프로그램 hang 현상에 대한 덤프 분석
... 91  92  93  94  95  96  97  98  99  100  [101]  102  103  104  105  ...