C++大整数运算（七）：有理数

C++大整数运算系列文章在前五节讲述了实现一个无符号大整数类的基本方法，第六节介绍了如何使用无符号大整数实现一个带符号大整数类。 本文的目的是介绍有理数类的实现方法。

在数学上，可以表达为两个整数的比（a/b 且 b不为0）的数被定义为有理数。 为了便于统一表示和方便计算，我们规定有理数必须表示为其最简形式（比如2/4应当表示为1/2），整数的分母必须为1。 有了之前大整数类的工作基础，我们可以通过采用两个带符号大整数来表示有理数，也可以通过两个无符号大整数和一个符号位来表示有理数，考虑到二者编程难度相似且后者效率可能会更高一些，因此本文采用两个无符号大整数和一个符号位来表示。

目录

• C++大整数运算（一）：概述
• C++大整数运算（二）：加法和减法
• C++大整数运算（三）：乘法
• C++大整数运算（四）：除法
• C++大整数运算（五）：进制转换
• C++大整数运算（六）：带符号大整数
• C++大整数运算（七）：有理数
• C++大整数运算（八）：总结

为了行文方便，我们假定无符号大整数类为ubigint， 有理数类为rational。因此，一个有理数类可以描述为以下代码：

class rational {
private:
    ubigint num; // 分子
    ubigint den; // 分母
    bool sign;
};

我们使用和带符号大整数相同的符号表示，当符号位为true时表示负数，当符号为false时表示正数，整数0表示为+0（即使0不是一个正数）。下面介绍如何实现四则运算。

加法

由于有了无符号大整数和带符号大整数的基础，基本上只需要按照我们在课本上学习到的分数运算来计算就可以了， 即b/a + d/c = (bc+ad)/(ac)。 假如a和c很大且有一个较大的公约数，那么乘法可能会耗费很多时间，因此可以首先计算出它们的最大公约数以简化计算。 假设g = gcd(a, c)，则b/a + d/c = (bc+ad)/(ac) = (bc/g + da/g)/(ac/g)。 通分之后的运算与带符号大整数相似，此处省略解释，只给出一种可行的实现。

rational add(rational r1, rational r2)
{
    ubigint g = gcd(r1.den, r2.den);
    ubigint ag = r1.den/g, cg = r2.den/g;
    rational result;
    const ubigint &b = r1.num, &d = r2.num;
    result.den = ag * rat.den;
    if(r1.sign == r2.sign)
    {
        result.num = b * cg + d * ag;
        result.sign = r1.sign;
    }
    else
    {
        ubigint bcg = b * cg, dag = d * ag;
        if(bcg >= dag)
        {
            result.num = bcg - dag;
            result.sign = r1.sign;
        }
        else
        {
            result.num = dag - bcg;
            result.sign = !r1.sign;
        }
    }
    // 由于求和后的分数可能不是最简表示
    // 实现一个函数来将分数化简成符合之前规定的唯一表示方法
    // 记得处理 -0 的表示
    result.reduce();
    return result;
}

减法

由于 a – b = a + (-b)，因此在有了加法的实现方法以后，可以很容易地实现减法，和带符号大整数一样，此处忽略减法的实现细节。

乘法

相比于加法来说，乘法则简单的多。假设两个乘数分别为r1 和r2。则结果的绝对值为(r1.num*r2.nun)/(r1.den*r2.den)。若r1和r2符号相同，则结果为正；若符号不同，则结果为负，注意处理好数0的表示即可。

rational multi(rational r1, rational r2)
{
    rational result;
    if(r1 == 0 || r2 == 0) result = 0;
    else
    {
        result.num = r1.num * r2.num;
        result.den = r1.den * r2.den;
        if(r1.sign == r2.sign) result.sign = false;
        else result.sign = true;
    }
    result.reduce();
    return result;
}

这种方法可以正确地算出结果，但不一定是最好的方法，假设要计算的为(a/b) * (b/a)， 上述的方法要先计算两次大整数乘法，再去约分，可能会花费很多的时间，另一种方式是先进行约分再计算乘法。即b/a * d/c = d/a * b/c，由于b/a和d/c已经是最简分数，而d/a和b/c则不一定。

rational multi2(rational r1, rational r2)
{
    rational result;
    if(r1 == 0 || r2 == 0) result = 0;
    else
    {
        const ubigint &a = r1.den, &b = r1.num, &c = r2.den, &d = r2.num;
        ubigint g1 = gcd(a, d), g2 = gcd(c, b);
        result.num = (b/g2) * (d/g1);
        result.den = (a/g1) * (c/g2);
        result.sign = r1.sign ^ r2.sign; // 可以使用异或而不是if
    }
    // 此时已经不需要化简
    return result;
}

注： 作者并未测试这两种方式的效率。

除法

分数的除法则不像带符号整数那样复杂，因为a / b = a * (1/b)，而取倒数对分数来说是一件简单的事，所以可以采用和乘法相似的方法处理乘法，但要注意除数为零的情况。

最大公约数

由于分数计算过程中需要约分，而约分需要求两个无符号大整数的最大公约数（Greatest Common Divisor），此处简单给出计算最大公约数的方法。 经典的求最大公约数的算法为欧几里得算法，又称辗转相除法，其原理为gcd(a, b) = gcd(b, a%b)。

// 递归
ubigint gcd(ubigint a, ubigint b)
{
    if(b == 0) return a;
    return gcd(b, a%b);
}
// 迭代
ubigint gcd(ubigint a, ubigint b)
{
    if(a > b) swap(a, b);
    while(a != 0)
    {
        ubigint q = b % a;
        b = a;
        a = q;
    }
    return b;
}

至此，有理数类的四则运算已经介绍完了，限于篇幅可能忽略了一些细节，有需要的读者可以到这里查看完整代码。