C++에서 부동 소수점 숫자의 최대공약수(GCD) 구하기

이 튜토리얼에서는 C++를 사용하여 부동 소수점(floating point) 숫자의 최대공약수(GCD, Greatest Common Divisor)를 구하는 프로그램을 살펴봅니다.

일반적인 정수의 GCD와 달리, 실수에 대한 GCD는 오차 범위를 고려해야 하기 때문에 접근 방식이 조금 다릅니다. 여기서는 두 개의 실수가 주어졌을 때, 해당 숫자들의 최대공약수를 계산하는 것이 우리의 목표입니다.

접근 방식

부동 소수점 숫자의 GCD는 유클리드 호제법(Euclidean Algorithm)을 재귀적으로 확장하여 구할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 두 수 중 큰 수를 기준으로, 작은 수가 충분히 작아질 때까지(오차 허용 범위인 0.001 미만) 나눗셈의 나머지 연산을 반복합니다.
• 나머지는 a - floor(a / b) * b 형태로 계산하며, 이는 실수 나눗셈의 나머지를 구하는 방식입니다.
• 재귀 호출이 종료되면 마지막 남은 값이 곧 두 실수의 GCD가 됩니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;

// 주어진 두 실수의 GCD를 반환하는 함수
double gcd(double a, double b){
    if (a < b)
        return gcd(b, a);
    if (fabs(b) < 0.001)
        return a;
    else
        return (gcd(b, a - floor(a / b) * b));
}

int main(){
    double a = 1.20, b = 22.5;
    cout << gcd(a, b);
    return 0;
}

실행 결과

0.3

코드 동작 원리

위 코드에서 gcd() 함수는 먼저 a가 b보다 작은 경우 두 값을 서로 교환하여 항상 큰 값이 앞에 오도록 합니다. 그다음 fabs(b)의 절댓값이 0.001보다 작은지 확인하는데, 이는 부동 소수점 연산 특성상 완전한 0이 되기 어렵기 때문에 일정 오차 범위 내라면 나머지가 0으로 간주하고 재귀를 종료하기 위함입니다.

조건에 해당하지 않으면 floor(a / b)를 이용해 몫을 구하고, a - floor(a / b) * b로 나머지를 계산한 뒤 자기 자신을 다시 호출합니다. 이 과정을 반복하면 결국 1.20과 22.5의 공통 약수인 0.3이 결과로 출력됩니다.