Calculate GCD in 3 ways

작성일 | In , |

Calculate GCD in 3 ways in C++

코드 소개

  • C++언어를 이용하여 두 자연수 a, b의 최대공약수(GCD)를 3가지 방법으로 구하고, 그 시간을 측정하는 프로그램이다.
    • gcd_sub(a, b) 큰 수에서 작은 수를 반복적으로 빼가면서 GCD 계산
    • gcd_mod(a, b) 큰 수를 작은 수로 나눈 나머지를 이용하여 GCD 계산
    • gcd_rec(a, b) gcd_sub(a, b)를 재귀함수로 만든것을 이용하여 GCD 계산
  • 각 방법에 소요되는 시간을 측정하기 위해 각 방법에 대한 계산을 10,000,000번 하도록 한다.

최대공약수(GCD; Greatest Common Divisor)

  • 어떠한 자연수들을 공통적으로 나눌 수 있는 수 중, 가장 큰 수이다.
  • 예를 들어 18, 24, 36의 최대공약수는 6이다.

코드

//============================================================================
// Name        : GCD3ways.cpp
// Author      : Minsu Jo
// Created on  : 2017. 11. 2.
// Description : Ansi-style
//============================================================================

/* Calculate GCD with 3 ways */

#include <iostream>
#include <sys/time.h> // include for elapsed-time measurement

using namespace std;

void gcd_sub(int a, int b);
void gcd_mod(int a, int b);
void gcd_rec1(int a, int b);
int gcd_rec2(int a, int b);
void print(timeval t_start, timeval t_end, string way, int gcd_result);

const int REPEATCOUNT = 10000000; // number of repetitions

int main()
{
    int a, b; // 2 non-negative integers(you input)

    cin >> a >> b;

    gcd_sub(a, b); // get GCD
    gcd_mod(a, b); // get GCD
    gcd_rec1(a, b); // get GCD

    return 0;
}

void gcd_sub(int a, int b)
{
    int gcd_result;
    timeval t_start, t_end; // start-time and end-time

    gettimeofday(&t_start, NULL); // start chronometry
    for(int i = 0; i < REPEATCOUNT; i++) // calculate GCD 'REPEATCOUNT' times
    {
        while(a != 0 && b != 0)
        {
            if(a > b) a -= b;
            else b -= a;
        }
        gcd_result = a + b;
    }
    gettimeofday(&t_end, NULL); // end chronometry

    print(t_start, t_end, "sub", gcd_result);
}

void gcd_mod(int a, int b)
{
    int gcd_result;
    timeval t_start, t_end; // start-time and end-time

    gettimeofday(&t_start, NULL); // start chronometry
    for(int i = 0; i < REPEATCOUNT; i++) // calculate GCD 'REPEATCOUNT' times
    {
        while(a != 0 && b != 0)
        {
            if(a > b) a %= b;
            else b %= a;
        }
        gcd_result = a + b;
    }
    gettimeofday(&t_end, NULL); // end chronometry

    print(t_start, t_end, "mod", gcd_result);
}

void gcd_rec1(int a, int b)
{
    int gcd_result;
    timeval t_start, t_end; // start-time and end-time

    gettimeofday(&t_start, NULL); // start chronometry
    for(int i = 0; i < REPEATCOUNT; i++) // calculate GCD 'REPEATCOUNT' times
    {
        gcd_result = gcd_rec2(a, b);
    }
    gettimeofday(&t_end, NULL); // end chronometry

    print(t_start, t_end, "rec", gcd_result);
}

int gcd_rec2(int a, int b)
{
    if(a == b) return a;
    else if(a > b) return gcd_rec2(a - b, b);
    else return gcd_rec2(a, b - a);
}

void print(timeval t_start, timeval t_end, string way, int gcd_result)
{
    double elapsedTime; // the time elapsed

    elapsedTime = (t_end.tv_sec - t_start.tv_sec) * 1000.0; // sec to ms
    elapsedTime += (t_end.tv_usec - t_start.tv_usec) / 1000.0; // us to ms

    cout << "Computing Time = " << elapsedTime << "ms";
    cout << ", GCD("<< way <<") : " << gcd_result << endl;
}

입력 데이터

2468 6428

실행결과

Computing Time = 15.97ms, GCD(sub) : 4
Computing Time = 15.723ms, GCD(mod) : 4
Computing Time = 1074.36ms, GCD(rec) : 4
0%