유클리드 호제법

//
//      EUCLID1.C : Implementation of Euclid's Algorithm
//
//                      Programmed By Clipper
//  Copyright ⓒ 2007 LaLuna All Rights Reserved.
//

#include <stdio.h>
#include "timer.h"

int get_gcd(int u, int v);          //뻴셈만을 이용한 유클리드 : 최대공약수
int gcd_modulus(int u, int v);      //나머지연산을 이용한 유클리드 : 최대공약수
int gcd_recursion(int u, int v);    //재귀호출을 이용한 유클리드 : 최대공약수

#define LOOF 10000000               //함수의 성능 테스트를 위한 반복 횟수

int main(int argc, char *argv[])
{
    int u, v, temp;
    clock_t t1, t2;                 //함수 측정시간을 정하기 위한 변수
    float result1 = 0, result2 = 0, result3 = 0;//함수 측정시간을 저장하기 위한 변수
    int i;
    
    puts("\n EUCLID1 : 두 양수의 최대 공약수 찾기 ");
    puts("\n           0을 입력하면 종료");
    
    while(1)
    {
        puts("\n\n 두 양수를 입력하세요 -> ");
        scanf("%d %d", &u, &v);
        
        if(u < 0 || v < 0)//음수의 입력은 무효로 한다.
        {
            puts("음수를 입력하셨습니다. 양수를 입력하세요\n");
            continue;
        }
        if(u == 0 || v == 0)//0이 입력되면 종료한다.
        {
            puts("0을 입력하셨습니다. 프로그램을 종료하겠습니다.\n");
            break;
        }
        t1 = clock();
        for(i=0;i<LOOF;i++)
        {
            temp = get_gcd(u,v);
        }
        t2 = clock();
        result1 = diff_clock(t1,t2);//빼기, 교환 함수 시간 측정
        t1 = clock();
        for(i=0;i<:LOOF;i++)
        {
            temp = gcd_modulus(u,v);
        }
        t2 = clock();
        result2 = diff_clock(t1,t2);//나머지 함수 시간 측정

        t1 = clock();
        for(i=0;i<LOOF;i++)
        {
            temp = gcd_recursion(u,v);
        }
        t2 = clock();
        result3 = diff_clock(t1,t2);//재귀호출 시간측정
                
        printf("두 양수 %d와 %d의 최대 공약수는 %d입니다.(뺄셈과 교환)\n", u, v, get_gcd(u,v));
        printf("두 양수 %d와 %d의 최대 공약수는 %d입니다.(나머지연산)\n", u, v, gcd_modulus(u,v));
        printf("두 양수 %d와 %d의 최대 공약수는 %d입니다.(재귀호출)\n", u, v, gcd_recursion(u,v));
        printf("빼기연산 : %5.2f 나머지 연산 : %5.2f 재귀호출 연산 : %5.2f", result1, result2, result3);
    }
    system("pause");
    return 0;
}

int get_gcd(int u, int v)
{
    int temp;
    while(u)//u가 0이면 v를 리턴, 아니면 루프를 돈다.
    {
        if(u < v)//u가 v보다 작으면 교환한다.
        {
            temp = u;
            u = v;
            v = temp;
        }
        u = u - v;
    }
    return v;
}

int gcd_modulus(int u, int v)
{
    int t;
    while(v)//v가 0이면 u를 리턴, 아니면 루프를 돈다.
    {
        t = u % v;
        u = v;
        v = t;
    }
    
    return u;
}
   
int gcd_recursion(int u, int v)
{
    if(v == 0)
    {
        return u;
    }
    else
    {
        return gcd_recursion(v, u%v);//재귀호출을 이용하여 나머지 연산
    }
}