irreducible_fraction.c

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

/*
 *  分数型
 */
struct fraction {
    int numerator;    /* 分子 */
    int denominator;  /* 分母 */
};

/*
 *  a と b の最大公約数を求める関数 gcd
 *  a と b が負の数でも通用する。
 *
 *  ----
 *
 *  これは、以下が自明であることを利用している
 *
 *  gcd(a, b) = gcd(-a, b) = gcd(a, -b) = gcd(-a, -b)
 *
 *  最大公約数を G (G > 0)とし、a = Ga' b= Gb' とすると、a と b の符号
 *  を入れ替えて如何に組み合わせても最大公約数はGとなる
 */
static int gcd(int a, int b)
{
    int tmp = 0;

    //   絶対値をとることで、a, b のいずれか、または
    //   両方が負であっても通用するようになる
    a = abs(a);
    b = abs(b);

    while (b != 0) {
        if (b < a) {
            // swap (abs(b) is always bigger than abs(a)
            tmp = a;
            a = b;
            b = tmp;
        }
        //
        // s/%/-/ は正しいが、b と a の値の差が圧倒的に大きい
        // ときにずっと同じ値 a を引きつづけるため、非常に遅い
        //
        // b の方が大きい限り a を引き続けるということは、いず
        // れは a で割った余りを求めることと同義になる。よって
        // b % a の方が圧倒的に速い
        //
        // ※  % 演算子のオペランドが負であったときの結果は処理系
        //     定義であることに注意。だが、ここでは a, b は常に
        //     正になるように補正しているので無問題
        //
        b = b % a;
        printf("a:%d b:%d\n", a, b);
    }
    return a;
}

/*
 *  既約分数に直す関数
 */
static void irreducible_fraction(struct fraction *f)
{
    assert(f->denominator != 0);

    //  既約分数を求める
    int g = gcd(f->numerator, f->denominator);
    f->numerator /= g;
    f->denominator /= g;

    //  分子も分母も負ならば
    //  正の数に直すべき
    if (f->numerator < 0 && f->denominator < 0) {
        f->numerator = 0 - f->numerator;
        f->denominator = 0 - f->denominator;
    }
}

/*
 *   argv[1] を分子、argv[2] を分母として
 *   既約分数を出力する
 */
int main(int argc, char *argv[])
{
    struct fraction f;

    //  no error processing
    f.numerator = atoi(argv[1]);
    f.denominator = atoi(argv[2]);
    irreducible_fraction(&f);

    printf("%d/%d\n", f.numerator, f.denominator);    
}

負の分数も扱えるようにしようぜ
./reduce -2 4

gcd(-3, 2) returns -1. Is it ok?